×

zbMATH — the first resource for mathematics

Homomorphisms of strongly regular graphs. (English) Zbl 1417.05252
Summary: We prove that if \(G\) and \(H\) are primitive strongly regular graphs with the same parameters and \(\varphi \) is a homomorphism from \(G\) to \(H\), then \(\varphi \) 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 P. J. Cameron and P. A. Kazanidis [J. Aust. Math. Soc. 85, No. 2, 145–154 (2008; Zbl 1167.05032)] 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.
MSC:
05E30 Association schemes, strongly regular graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
90C22 Semidefinite programming
05C15 Coloring of graphs and hypergraphs
Software:
Digraphs; SageMath
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Araújo, J.; Cameron, P. J.; Steinberg, B., Between primitive and 2-transitive: Synchronization and its friends, EMS Surveys in Mathematical Sciences, 4, 2, 101-184, (2017) · Zbl 1402.68124
[2] Cameron, P. J.; Kazanidis, P. A., Cores of symmetric graphs, Journal of the Australian Mathematical Society, 85, 2, 145-154, (2008) · Zbl 1167.05032
[3] Delsarte, P., An algebraic approach to the association schemes of coding theory, Philips Research Reports Suppl., 10, (1973) · Zbl 1075.05606
[4] Duval, A. M., A directed graph version of strongly regular graphs, Journal of Combinatorial Theory, Series A, 47, 1, 71-100, (1988) · Zbl 0642.05025
[5] Gardiner, A. D.; Godsil, C. D.; Hensel, A. D.; Royle, G. F., Second neighbourhoods of strongly regular graphs, Discrete Mathematics, 103, 2, 161-170, (1992) · Zbl 0764.05100
[6] Godsil, C. D.; Hobart, S. A.; Martin, W. J., Representations of directed strongly regular graphs, European Journal of Combinatorics, 28, 7, 1980-1993, (2007) · Zbl 1121.05078
[7] Godsil, C. D.; Roberson, D. E.; Rooney, B.; Šámal, R.; Varvitsiotis, A., Graph Homomorphisms via Vector Colorings, (2016) · Zbl 1414.05199
[8] Godsil, C. D.; Roberson, D. E.; Rooney, B.; Šámal, R.; Varvitsiotis, A., Universal Completability, Least Eigenvalue Frameworks, and Vector Colorings, Discrete & Computational Geometry, 58, 2, 265-292, (2017) · Zbl 1371.05162
[9] Godsil, C. D.; Roberson, D. E.; Rooney, B.; Šámal, R.; Varvitsiotis, A., Vector Coloring the Categorical Product of Graphs, (2018)
[10] Godsil, C. D.; Royle, G. F., Cores of Geometric Graphs, Annals of Combinatorics, 15, 2, 267-276, (2011) · Zbl 1234.05165
[11] Godsil, C. D.; Royle, G. F., Algebraic graph theory, 207, (2013), Springer Science & Business Media
[12] Haemers, W. H., Eigenvalue techniques in design and graph theory, (1979) · Zbl 0429.05013
[13] Hahn, G.; Tardif, C., Graph symmetry, Graph homomorphisms: structure and symmetry, 107-166, (1997), Springer · Zbl 0880.05079
[14] Hoffman, A. J., On eigenvalues and colorings of graphs, Graph Theory and its Applications, 79-91, (1970), Academic Press, New York · Zbl 0227.05105
[15] Huang, L.-P.; Huang, J.-Q.; Zhao, K., On endomorphisms of alternating forms graph, Discrete Mathematics, 338, 3, 110-121, (2015) · Zbl 1305.05151
[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, 45, 2, 246-265, (1998) · Zbl 0904.68116
[18] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1, 1-7, (1979) · Zbl 0395.94021
[19] Neumaier, A., Strongly regular graphs with smallest eigenvalue \(-m\), Archiv der Mathematik, 33, 1, 392-400, (1979) · Zbl 0407.05043
[20] Schrijver, A., A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory, 25, 4, 425-429, (1979) · Zbl 0444.94009
[21] Spence, E., Personal Webpage: Strongly Regular Graphs on at most 64 Vertices
[22] Szegedy, M., A note on the \(\vartheta \) number of Lovász and the generalized Delsarte bound, Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, (1994)
[23] The Sage Developers, Sage Mathematics Software (Version 6.9), (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.