Download PDF - Families of strongly projective graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Families of strongly projective graphs

Authors 1, 2

Affiliations

  1. Department of Mathematics, Champlain Regional College, 900 Riverside St-Lambert, QC, Canada, J4P 3P2
  2. Department of Mathematics and Statistics, Concordia University, 1455 de Maisonneuve West, Montréal, QC, Canada, H3G 1M8

Abstract

We give several characterisations of strongly projective graphs which generalise in many respects odd cycles and complete graphs [7]. We prove that all known families of projective graphs contain only strongly projective graphs, including complete graphs, odd cycles, Kneser graphs and non-bipartite distance-transitive graphs of diameter d ≥ 3.

Keywords

ENG
distance-transitive graphs, graph homomorphism, graph product

Bibliography

  1. D. Duffus, B. Sands and R.E. Woodrow, On the chromatic number of the product of graphs, J. Graph Theory 9 (1985) 487-495, doi: 10.1002/jgt.3190090409.
  2. M. El-Zahar and N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4, Combinatorica 5 (1985) 121-126, doi: 10.1007/BF02579374.
  3. D. Greenwell and L. Lovász, Applications of product colourings, Acta Math. Acad. Sci. Hungar. 25 (1974) 335-340, doi: 10.1007/BF01886093.
  4. G. Hahn and C. Tardif, Graph homomorphisms: structure and symmetry, in: G. Hahn and G. Sabidussi, eds, Graph Symmetry, Algebraic Methods and Applications, NATO ASI Ser. C 497 (Kluwer Academic Publishers, Dordrecht, 1997) 107-166.
  5. S. Hazan, On triangle-free projective graphs, Algebra Universalis, 35 (1996) 185-196, doi: 10.1007/BF01195494.
  6. W. Imrich and S. Klavžar, Product Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization (John Wiley and Sons, 2000).
  7. B. Larose, Strongly projective graphs, Canad. J. Math. 17 pages, to appear.
  8. B. Larose and C. Tardif, Hedetniemi's conjecture and the retracts of products of graphs, Combinatorica 20 (2000) 531-544, doi: 10.1007/s004930070006.
  9. B. Larose and C. Tardif, Strongly rigid graphs and projectivity, Mult. Val. Logic, 22 pages, to appear.
  10. B. Larose and C. Tardif, Projectivity and independent sets in powers of graphs, J. Graph Theory, 12 pages, to appear.
  11. L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hungar. 18 (1967) 321-328, doi: 10.1007/BF02280291.
  12. R.N. McKenzie, G.F. McNulty and W.F. Taylor, Algebras, Lattices and Varieties (Wadsworth and Brooks/Cole, Monterey California, 1987).
  13. J. Nesetril, X. Zhu, On sparse graphs with given colorings and homomorphisms, preprint, 13 pages, 2000.
  14. D.H. Smith, Primitive and imprimitive graphs, Quart. J. Math. Oxford (2) 22 (1971) 551-557, doi: 10.1093/qmath/22.4.551.
  15. A. Szendrei, Simple surjective algebras having no proper subalgebras, J. Austral. Math. Soc. (Series A) 48 (1990) 434-454, doi: 10.1017/S1446788700029979.
  16. C. Tardif, personal communication, 2000.
  17. J.W. Walker, From graphs to ortholattices and equivariant maps, J. Combin. Theory (B) 35 (1983) 171-192, doi: 10.1016/0095-8956(83)90070-9.
Discussiones Mathematicae Graph Theory
2002/22/2
Export to PBN, Opens in new tab
Pages:
271-292
Main language of publication
English
Received
2001-04-02
Accepted
2001-12-04
Published
2002

DOI: 10.7151/dmgt.1175

Exact and natural sciences