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.

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.