Families of strongly projective graphs

Benoit Larose

Discussiones Mathematicae Graph Theory (2002)

  • Volume: 22, Issue: 2, page 271-292
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Benoit Larose. "Families of strongly projective graphs." Discussiones Mathematicae Graph Theory 22.2 (2002): 271-292. <http://eudml.org/doc/270746>.

@article{BenoitLarose2002,
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.},
author = {Benoit Larose},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distance-transitive graphs; graph homomorphism; graph product; Strongly projective; product graph; distance-transitive},
language = {eng},
number = {2},
pages = {271-292},
title = {Families of strongly projective graphs},
url = {http://eudml.org/doc/270746},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Benoit Larose
TI - Families of strongly projective graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 2
SP - 271
EP - 292
AB - 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.
LA - eng
KW - distance-transitive graphs; graph homomorphism; graph product; Strongly projective; product graph; distance-transitive
UR - http://eudml.org/doc/270746
ER -

References

top
  1. [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. Zbl0664.05019
  2. [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. Zbl0575.05028
  3. [3] D. Greenwell and L. Lovász, Applications of product colourings, Acta Math. Acad. Sci. Hungar. 25 (1974) 335-340, doi: 10.1007/BF01886093. Zbl0294.05108
  4. [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. [5] S. Hazan, On triangle-free projective graphs, Algebra Universalis, 35 (1996) 185-196, doi: 10.1007/BF01195494. Zbl0845.05062
  6. [6] W. Imrich and S. Klavžar, Product Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization (John Wiley and Sons, 2000). 
  7. [7] B. Larose, Strongly projective graphs, Canad. J. Math. 17 pages, to appear. Zbl1020.05029
  8. [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. Zbl0996.05065
  9. [9] B. Larose and C. Tardif, Strongly rigid graphs and projectivity, Mult. Val. Logic, 22 pages, to appear. Zbl1009.05121
  10. [10] B. Larose and C. Tardif, Projectivity and independent sets in powers of graphs, J. Graph Theory, 12 pages, to appear. Zbl1003.05077
  11. [11] L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hungar. 18 (1967) 321-328, doi: 10.1007/BF02280291. Zbl0174.01401
  12. [12] R.N. McKenzie, G.F. McNulty and W.F. Taylor, Algebras, Lattices and Varieties (Wadsworth and Brooks/Cole, Monterey California, 1987). Zbl0611.08001
  13. [13] J. Nesetril, X. Zhu, On sparse graphs with given colorings and homomorphisms, preprint, 13 pages, 2000. 
  14. [14] D.H. Smith, Primitive and imprimitive graphs, Quart. J. Math. Oxford (2) 22 (1971) 551-557, doi: 10.1093/qmath/22.4.551. Zbl0222.05111
  15. [15] A. Szendrei, Simple surjective algebras having no proper subalgebras, J. Austral. Math. Soc. (Series A) 48 (1990) 434-454, doi: 10.1017/S1446788700029979. Zbl0702.08003
  16. [16] C. Tardif, personal communication, 2000. 
  17. [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. Zbl0509.05059

NotesEmbed ?

top

You must be logged in to post comments.