Homomorphisms of strongly regular graphs

Roberson, David E.

doi:10.5802/alco.50

Roberson, David E.¹

¹ Technical University of Denmark Dept. of Applied Mathematics and Computer Science Richard Petersens Plads Lyngby DK-2400, Denmark

Algebraic Combinatorics, Volume 2 (2019) no. 4, pp. 481-497.

Abstract

We prove that if $G$ and $H$ are primitive strongly regular graphs with the same parameters and $φ$ is a homomorphism from $G$ to $H$ , then $φ$ is either an isomorphism or a coloring (homomorphism to a complete subgraph). Moreover, any such coloring is optimal for $G$ and its image is a maximum clique of $H$ . Therefore, the only endomorphisms of a primitive strongly regular graph are automorphisms or colorings. This confirms and strengthens a conjecture of Peter Cameron and Priscila Kazanidis that all strongly regular graphs are cores or have complete cores. The proof of the result is elementary, mainly relying on linear algebraic techniques. In the second half of the paper we discuss the idea underlying the proof, namely that it can be seen as a straightforward application of complementary slackness to a dual pair of semidefinite programs that define the Lovász theta function. We also consider implications of the result and show that essentially the same proof can be used to obtain a more general statement. We believe that one of the main contributions of the work is the novel proof technique, which is the first able to make use of the combinatorial regularity of a graph in order to obtain results about its endomorphisms/homomorphisms. Thus we expect this approach to have further applicability to the study of homomorphisms of highly regular graphs.

Received: 2017-10-20
Revised: 2018-11-22
Accepted: 2018-11-23
Published online: 2019-08-01

MR Zbl

DOI: 10.5802/alco.50

Classification: 05C50, 05C60, 90C22, 05C15
Keywords: Homomorphisms, strongly regular graphs, linear algebra, semidefinite programming, Lovász theta

Author's affiliations:

Roberson, David E. ¹

¹ Technical University of Denmark Dept. of Applied Mathematics and Computer Science Richard Petersens Plads Lyngby DK-2400, Denmark

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2019__2_4_481_0,
     author = {Roberson, David E.},
     title = {Homomorphisms of strongly regular graphs},
     journal = {Algebraic Combinatorics},
     pages = {481--497},
     publisher = {MathOA foundation},
     volume = {2},
     number = {4},
     year = {2019},
     doi = {10.5802/alco.50},
     zbl = {1417.05252},
     mrnumber = {3997507},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.50/}
}

TY  - JOUR
AU  - Roberson, David E.
TI  - Homomorphisms of strongly regular graphs
JO  - Algebraic Combinatorics
PY  - 2019
SP  - 481
EP  - 497
VL  - 2
IS  - 4
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.50/
DO  - 10.5802/alco.50
LA  - en
ID  - ALCO_2019__2_4_481_0
ER  -

%0 Journal Article
%A Roberson, David E.
%T Homomorphisms of strongly regular graphs
%J Algebraic Combinatorics
%D 2019
%P 481-497
%V 2
%N 4
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.50/
%R 10.5802/alco.50
%G en
%F ALCO_2019__2_4_481_0

Roberson, David E. Homomorphisms of strongly regular graphs. Algebraic Combinatorics, Volume 2 (2019) no. 4, pp. 481-497. doi : 10.5802/alco.50. https://alco.centre-mersenne.org/articles/10.5802/alco.50/

References
Cited by

[1] Araújo, J.; Cameron, P. J.; Steinberg, B. Between primitive and 2-transitive: Synchronization and its friends, EMS Surveys in Mathematical Sciences, Volume 4 (2017) no. 2, pp. 101-184 | DOI | MR | Zbl

[2] Cameron, P. J.; Kazanidis, P. A. Cores of symmetric graphs, Journal of the Australian Mathematical Society, Volume 85 (2008) no. 2, pp. 145-154 | DOI | MR | Zbl

[3] Delsarte, P. An algebraic approach to the association schemes of coding theory, Philips Research Reports Suppl., Volume 10 (1973) | MR | Zbl

[4] Duval, A. M. A directed graph version of strongly regular graphs, Journal of Combinatorial Theory, Series A, Volume 47 (1988) no. 1, pp. 71-100 | DOI | MR | Zbl

[5] Gardiner, A. D.; Godsil, C. D.; Hensel, A. D.; Royle, G. F. Second neighbourhoods of strongly regular graphs, Discrete Mathematics, Volume 103 (1992) no. 2, pp. 161-170 | DOI | MR | Zbl

[6] Godsil, C. D.; Hobart, S. A.; Martin, W. J. Representations of directed strongly regular graphs, European Journal of Combinatorics, Volume 28 (2007) no. 7, pp. 1980-1993 | DOI | MR | Zbl

[7] Godsil, C. D.; Roberson, D. E.; Rooney, B.; Šámal, R.; Varvitsiotis, A. Graph Homomorphisms via Vector Colorings (2016) (https://arxiv.org/abs/1610.10002) | Zbl

[8] Godsil, C. D.; Roberson, D. E.; Rooney, B.; Šámal, R.; Varvitsiotis, A. Universal Completability, Least Eigenvalue Frameworks, and Vector Colorings, Discrete & Computational Geometry, Volume 58 (2017) no. 2, pp. 265-292 | DOI | MR | Zbl

[9] Godsil, C. D.; Roberson, D. E.; Rooney, B.; Šámal, R.; Varvitsiotis, A. Vector Coloring the Categorical Product of Graphs (2018) (https://arxiv.org/abs/1801.08243)

[10] Godsil, C. D.; Royle, G. F. Cores of Geometric Graphs, Annals of Combinatorics, Volume 15 (2011) no. 2, pp. 267-276 | DOI | MR | Zbl

[11] Godsil, C. D.; Royle, G. F. Algebraic graph theory, 207, Springer Science & Business Media, 2013

[12] Haemers, W. H. Eigenvalue techniques in design and graph theory, Ph. D. Thesis, Eindhoven University of Technology (Netherlands) (1979) | Zbl

[13] Hahn, G.; Tardif, C. Graph homomorphisms: structure and symmetry, Graph symmetry, Springer, 1997, pp. 107-166 | DOI | Zbl

[14] Hoffman, A. J. On eigenvalues and colorings of graphs, Graph Theory and its Applications (1970), pp. 79-91

[15] Huang, L.-P.; Huang, J.-Q.; Zhao, K. On endomorphisms of alternating forms graph, Discrete Mathematics, Volume 338 (2015) no. 3, pp. 110-121 | DOI | MR

[16] Jonušas, J.; Mitchell, J. D.; Torpey, M.; Wilson, W. Digraphs – GAP package, Version 0.2 (2015)

[17] Karger, D.; Motwani, R.; Sudan, M. Approximate graph coloring by semidefinite programming, J. ACM, Volume 45 (1998) no. 2, pp. 246-265 | DOI | MR | Zbl

[18] Lovász, L. On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, Volume 25 (1979) no. 1, pp. 1-7 | DOI | MR | Zbl

[19] Neumaier, A. Strongly regular graphs with smallest eigenvalue $- m$ , Archiv der Mathematik, Volume 33 (1979) no. 1, pp. 392-400 | DOI | MR | Zbl

[20] Schrijver, A. A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory, Volume 25 (1979) no. 4, pp. 425-429 | DOI | Zbl

[21] Spence, E. Personal Webpage: Strongly Regular Graphs on at most 64 Vertices (http://www.maths.gla.ac.uk/~es/srgraphs.php)

[22] Szegedy, M. A note on the $ϑ$ number of Lovász and the generalized Delsarte bound, Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (1994) | DOI

[23] The Sage Developers Sage Mathematics Software (Version 6.9) (2015) (http://www.sagemath.org)

Cited by Sources: