On cyclically embeddable graphs

Mariusz Woźniak

Discussiones Mathematicae Graph Theory (1999)

  • Volume: 19, Issue: 2, page 241-248
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Mariusz Woźniak. "On cyclically embeddable graphs." Discussiones Mathematicae Graph Theory 19.2 (1999): 241-248. <http://eudml.org/doc/270478>.

@article{MariuszWoźniak1999,
abstract = {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.},
author = {Mariusz Woźniak},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {packing of graphs; unicyclic graphs; cyclic permutation; packing; embedding; embeddable graphs},
language = {eng},
number = {2},
pages = {241-248},
title = {On cyclically embeddable graphs},
url = {http://eudml.org/doc/270478},
volume = {19},
year = {1999},
}

TY - JOUR
AU - Mariusz Woźniak
TI - On cyclically embeddable graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1999
VL - 19
IS - 2
SP - 241
EP - 248
AB - 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.
LA - eng
KW - packing of graphs; unicyclic graphs; cyclic permutation; packing; embedding; embeddable graphs
UR - http://eudml.org/doc/270478
ER -

References

top
  1. [1] B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978). 
  2. [2] B. Bollobás and S.E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory 25 (B) (1978) 105-124. Zbl0387.05020
  3. [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. Zbl0375.05046
  4. [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. Zbl0379.05023
  5. [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. Zbl0479.05028
  6. [6] T. Gangopadhyay, Packing graphs in their complements, Discrete Math. 186 (1998) 117-124, doi: 10.1016/S0012-365X(97)00186-6. Zbl0958.05111
  7. [7] B. Ganter, J. Pelikan and L. Teirlinck, Small sprawling systems of equicardinal sets, Ars Combinatoria 4 (1977) 133-142. Zbl0418.05003
  8. [8] N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory 25 (B) (1978) 295-302. Zbl0417.05037
  9. [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. Zbl0391.05047
  10. [10] M. Woźniak, Embedding graphs of small size, Discrete Applied Math. 51 (1994) 233-241, doi: 10.1016/0166-218X(94)90112-0. Zbl0807.05025
  11. [11] M. Woźniak, Packing three trees, Discrete Math. 150 (1996) 393-402, doi: 10.1016/0012-365X(95)00204-A. 
  12. [12] M. Woźniak, Packing of Graphs, Dissertationes Mathematicae 362 (1997) pp.78. 
  13. [13] H.P. Yap, Some Topics in Graph Theory (London Mathematical Society, Lectures Notes Series 108, Cambridge University Press, Cambridge 1986). Zbl0588.05002
  14. [14] H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404, doi: 10.1016/0012-365X(88)90232-4. Zbl0685.05036

NotesEmbed ?

top

You must be logged in to post comments.