Distance-regular graphs with complete multipartite μ -graphs and AT4 family
Aleksandar Jurišić1
and Jack Koolen2
1Faculty of Computer and Information Sciences Tr {z}a {s}ka 25 1000 Ljubljana Slovenija Tr {z}a {s}ka 25 1000 Ljubljana Slovenija
2POSTECH Department of Mathematics 790-784 Pohang South Korea 790-784 Pohang South Korea
2POSTECH Department of Mathematics 790-784 Pohang South Korea 790-784 Pohang South Korea
DOI: 10.1007/s10801-006-0046-z
Abstract
Let Γ be an antipodal distance-regular graph of diameter 4, with eigenvalues $\theta_0>\theta_1>\theta_2>\theta_3>\theta_4$ \theta_0>\theta_1>\theta_2>\theta_3>\theta_4. Then its Krein parameter q 11 4 q_{11}^4 vanishes precisely when Γ is tight in the sense of Jurišić, Koolen and Terwilliger, and furthermore, precisely when Γ is locally strongly regular with nontrivial eigenvalues p:= q 2 p:=\theta_2 and - q:= q 3 -q:=\theta_3. When this is the case, the intersection parameters of Γ can be parametrized by p, q and the size of the antipodal classes r of Γ .
Let Γ be an antipodal tight graph of diameter 4, denoted by AT4 (p, q, r), and let the μ -graph be a graph that is induced by the common neighbours of two vertices at distance 2. Then we show that all the μ -graphs of Γ are complete multipartite if and only if Γ is AT4( sq, q, q) for some natural number s. As a consequence, we derive new existence conditions for graphs of the AT4 family whose μ -graphs are not complete multipartite. Another interesting application of our results is also that we were able to show that the μ -graphs of a distance-regular graph with the same intersection array as the Patterson graph are the complete bipartite graph K 4,4.
Pages: 459–471
Keywords: keywords distance-regular graphs; antipodal; tight; locally strongly regular; $μ$-graphs; AT4 family
Full Text: PDF
References
1. A.E. Brouwer, “Strongly regular graphs,” in: The CRC Handbook of Combinatorial Designs, (C.J. Colbourn and J.H. Dinitz (Eds.), CRC Press, 1996, pp. 667-685.
2. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, Heidelberg, Berlin, Heidelberg, (1989) (for corrections and additions see http://www.win.tue.nl/math/ dw/personalpages/aeb/drg/index.html
3. A.E. Brouwer, A. Juri\check sić and J.H. Koolen, Characterization of the Patterson graph, in preparation.
4. J.T.M. van Bon and R. Weiss, “An existence lemma for groups generated by 3-transpositions,” Invent. Math. 109, (1992) 519-534.
5. C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
6. A. Juri\check sić, “AT4 family and 2-homogeneous graphs,” Discrete Math. 264(1-3) (2003), 127-148.
7. A. Juri\check sić and J. Koolen, “Nonexistence of some antipodal distance-regular graphs of diameter four,” Europ. J. Combin. 21 (2000), 1039-1046.
8. A. Juri\check sić and J. Koolen, “Classification of the AT4(qs, q, q) family of distance-regular graphs,” in preparation.
9. A. Juri\check sić, J. Koolen, and P. Terwilliger, “Tight distance-regular graphs,” J. Alg. Combin. 12 (2000), 163-197.
10. A. Juri\check sić and J. Koolen, “A local approach to 1-homogeneous graphs,” Designs, Codes and Cryptography 21 (2000), 127-147.
11. A. Juri\check sić and J. Koolen, “Krein parameters and antipodal tight graphs with diameter 3 and 4,” Discrete Math. 244 (2002), 181-202.
12. A. Juri\check sić and J. Koolen, “1-homogeneous graphs with Cocktail Party μ-graphs,” J. Alg. Combin. 18 (2003), 79-98.
13. T. Meixner, “Some polar towers,” Europ. J. Combin. 12 (1991), 397-415.
14. K. Nomura, “Homogeneous graphs and regular near polygons,” J. Combin. Theory Ser. B 60 (1994), 63-71. Springer
15. M. Sch\ddot onert et al., GAP-Groups, Algorithms and Programming, 4th edition, Lehrstuhl D f\ddot ur Mathe- matik, RWTH Aachen, 1994.
16. S. Rees and L.H. Soicher, “An algorithmic approach to fundamental groups and covers of combinatorial cell complexes,” Symbolic Computation 29 (2000), 59-77.
17. L.H. Soicher, “GRAPE: A system for computing with graphs and groups,” in Groups and Computation, L. Finkelstein and W.M. Kantor (Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science vol. 11, A.M.S. 1993 pp. 287-291.
18. L.H. Soicher, “Three new distance-regular graphs,” Europ. J. Combin. 14 (1993), 501-505.
19. M. Suzuki, “A finite simple group of order 448,345,497,600” in Symposium on Finite Groups, R. Bauer and C. Sah (Eds), Benjamin, New York, 1969, pp. 113-119.
2. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, Heidelberg, Berlin, Heidelberg, (1989) (for corrections and additions see http://www.win.tue.nl/math/ dw/personalpages/aeb/drg/index.html
3. A.E. Brouwer, A. Juri\check sić and J.H. Koolen, Characterization of the Patterson graph, in preparation.
4. J.T.M. van Bon and R. Weiss, “An existence lemma for groups generated by 3-transpositions,” Invent. Math. 109, (1992) 519-534.
5. C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
6. A. Juri\check sić, “AT4 family and 2-homogeneous graphs,” Discrete Math. 264(1-3) (2003), 127-148.
7. A. Juri\check sić and J. Koolen, “Nonexistence of some antipodal distance-regular graphs of diameter four,” Europ. J. Combin. 21 (2000), 1039-1046.
8. A. Juri\check sić and J. Koolen, “Classification of the AT4(qs, q, q) family of distance-regular graphs,” in preparation.
9. A. Juri\check sić, J. Koolen, and P. Terwilliger, “Tight distance-regular graphs,” J. Alg. Combin. 12 (2000), 163-197.
10. A. Juri\check sić and J. Koolen, “A local approach to 1-homogeneous graphs,” Designs, Codes and Cryptography 21 (2000), 127-147.
11. A. Juri\check sić and J. Koolen, “Krein parameters and antipodal tight graphs with diameter 3 and 4,” Discrete Math. 244 (2002), 181-202.
12. A. Juri\check sić and J. Koolen, “1-homogeneous graphs with Cocktail Party μ-graphs,” J. Alg. Combin. 18 (2003), 79-98.
13. T. Meixner, “Some polar towers,” Europ. J. Combin. 12 (1991), 397-415.
14. K. Nomura, “Homogeneous graphs and regular near polygons,” J. Combin. Theory Ser. B 60 (1994), 63-71. Springer
15. M. Sch\ddot onert et al., GAP-Groups, Algorithms and Programming, 4th edition, Lehrstuhl D f\ddot ur Mathe- matik, RWTH Aachen, 1994.
16. S. Rees and L.H. Soicher, “An algorithmic approach to fundamental groups and covers of combinatorial cell complexes,” Symbolic Computation 29 (2000), 59-77.
17. L.H. Soicher, “GRAPE: A system for computing with graphs and groups,” in Groups and Computation, L. Finkelstein and W.M. Kantor (Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science vol. 11, A.M.S. 1993 pp. 287-291.
18. L.H. Soicher, “Three new distance-regular graphs,” Europ. J. Combin. 14 (1993), 501-505.
19. M. Suzuki, “A finite simple group of order 448,345,497,600” in Symposium on Finite Groups, R. Bauer and C. Sah (Eds), Benjamin, New York, 1969, pp. 113-119.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition