Download PDF - On cyclically embeddable (n,n)-graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On cyclically embeddable (n,n)-graphs

Authors 1, 1, 1

Affiliations

  1. Faculty of Applied Mathematics AGH, Department of Discrete Mathematics, al. Mickiewicza 30, 30-059 Kraków, Poland

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.

Keywords

ENG
packing of graphs, cyclic permutation

Bibliography

  1. B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978).
  2. B. Bollobás and S.E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory 25 (B) (1978) 105-124.
  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.
  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.
  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.
  6. T. Gangopadhyay, Packing graphs in their complements, Discrete Math. 186 (1998) 117-124, doi: 10.1016/S0012-365X(97)00186-6.
  7. B. Ganter, J. Pelikan and L. Teirlinck, Small sprawling systems of equicardinal sets, Ars Combin. 4 (1977) 133-142.
  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.
  9. M. Woźniak, Packing of Graphs, Dissertationes Math. 362 (1997) pp.78.
  10. M. Woźniak, On cyclically embeddable graphs, Discuss. Math. Graph Theory 19 (1999) 241-248, doi: 10.7151/dmgt.1099.
  11. M. Woźniak, On cyclically embeddable (n,n-1)-graphs, Discrete Math. 251 (2002) 173-179.
  12. H.P. Yap, Some Topics In Graph Theory, London Mathematical Society, Lectures Notes Series 108 (Cambridge University Press, Cambridge, 1986).
  13. H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404.
Discussiones Mathematicae Graph Theory
2003/23/1
Export to PBN, Opens in new tab
Pages:
85-104
Main language of publication
English
Received
2001-07-05
Accepted
2002-03-04
Published
2003

DOI: 10.7151/dmgt.1187

Exact and natural sciences