On cyclically embeddable graphs
Mariusz Woźniak
Discussiones Mathematicae Graph Theory, Tome 19 (1999), p. 241-248 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

An embedding of a simple graph G into its complement G̅ is a permutation σ on V(G) such that if an edge xy belongs to E(G), then σ(x)σ(y) does not belong to E(G). In this note we consider some families of embeddable graphs such that the corresponding permutation is cyclic.

Publié le : 1999-01-01
EUDML-ID : urn:eudml:doc:270478 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1099,
     author = {Mariusz Wo\'zniak},
     title = {On cyclically embeddable graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {19},
     year = {1999},
     pages = {241-248},
     zbl = {0958.05041},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1099}
}

Mariusz Woźniak. On cyclically embeddable graphs. Discussiones Mathematicae Graph Theory, Tome 19 (1999) pp. 241-248. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1099/

[000] [1] B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978).

[001] [2] B. Bollobás and S.E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory 25 (B) (1978) 105-124. | Zbl 0387.05020

[002] [3] D. Burns and S. Schuster, Every (p,p-2) graph is contained in its complement, J. Graph Theory 1 (1977) 277-279, doi: 10.1002/jgt.3190010308. | Zbl 0375.05046

[003] [4] D. Burns and S. Schuster, Embedding (n,n-1) graphs in their complements, Israel J. Math. 30 (1978) 313-320, doi: 10.1007/BF02761996. | Zbl 0379.05023

[004] [5] R.J. Faudree, C.C. Rousseau, R.H. Schelp and S. Schuster, Embedding graphs in their complements, Czechoslovak Math. J. 31:106 (1981) 53-62. | Zbl 0479.05028

[005] [6] T. Gangopadhyay, Packing graphs in their complements, Discrete Math. 186 (1998) 117-124, doi: 10.1016/S0012-365X(97)00186-6. | Zbl 0958.05111

[006] [7] B. Ganter, J. Pelikan and L. Teirlinck, Small sprawling systems of equicardinal sets, Ars Combinatoria 4 (1977) 133-142. | Zbl 0418.05003

[007] [8] N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory 25 (B) (1978) 295-302. | Zbl 0417.05037

[008] [9] S. Schuster, Fixed-point-free embeddings of graphs in their complements, Internat. J. Math. & Math. Sci. 1 (1978) 335-338, doi: 10.1155/S0161171278000356. | Zbl 0391.05047

[009] [10] M. Woźniak, Embedding graphs of small size, Discrete Applied Math. 51 (1994) 233-241, doi: 10.1016/0166-218X(94)90112-0. | Zbl 0807.05025

[010] [11] M. Woźniak, Packing three trees, Discrete Math. 150 (1996) 393-402, doi: 10.1016/0012-365X(95)00204-A.

[011] [12] M. Woźniak, Packing of Graphs, Dissertationes Mathematicae 362 (1997) pp.78.

[012] [13] H.P. Yap, Some Topics in Graph Theory (London Mathematical Society, Lectures Notes Series 108, Cambridge University Press, Cambridge 1986). | Zbl 0588.05002

[013] [14] H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404, doi: 10.1016/0012-365X(88)90232-4. | Zbl 0685.05036