On cyclically embeddable (n,n)-graphs

Agnieszka Görlich; Monika Pilśniak; Mariusz Woźniak

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 1, page 85-104
  • 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 the embeddable (n,n)-graphs. We prove that with few exceptions the corresponding permutation may be chosen as cyclic one.

How to cite

top

Agnieszka Görlich, Monika Pilśniak, and Mariusz Woźniak. "On cyclically embeddable (n,n)-graphs." Discussiones Mathematicae Graph Theory 23.1 (2003): 85-104. <http://eudml.org/doc/270699>.

@article{AgnieszkaGörlich2003,
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 the embeddable (n,n)-graphs. We prove that with few exceptions the corresponding permutation may be chosen as cyclic one.},
author = {Agnieszka Görlich, Monika Pilśniak, Mariusz Woźniak},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {packing of graphs; cyclic permutation; packing},
language = {eng},
number = {1},
pages = {85-104},
title = {On cyclically embeddable (n,n)-graphs},
url = {http://eudml.org/doc/270699},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Agnieszka Görlich
AU - Monika Pilśniak
AU - Mariusz Woźniak
TI - On cyclically embeddable (n,n)-graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 1
SP - 85
EP - 104
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 the embeddable (n,n)-graphs. We prove that with few exceptions the corresponding permutation may be chosen as cyclic one.
LA - eng
KW - packing of graphs; cyclic permutation; packing
UR - http://eudml.org/doc/270699
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 Combin. 4 (1977) 133-142. Zbl0418.05003
  8. [8] 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
  9. [9] M. Woźniak, Packing of Graphs, Dissertationes Math. 362 (1997) pp.78. 
  10. [10] M. Woźniak, On cyclically embeddable graphs, Discuss. Math. Graph Theory 19 (1999) 241-248, doi: 10.7151/dmgt.1099. Zbl0958.05041
  11. [11] M. Woźniak, On cyclically embeddable (n,n-1)-graphs, Discrete Math. 251 (2002) 173-179. Zbl1001.05101
  12. [12] H.P. Yap, Some Topics In Graph Theory, London Mathematical Society, Lectures Notes Series 108 (Cambridge University Press, Cambridge, 1986). Zbl0588.05002
  13. [13] H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404. Zbl0685.05036

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.