Smith's Theorem and a characterization of the 6-cube as distance-transitive graph
M.R. Alfuraidan1
and J.I. Hall2
1Department of Mathematical Sciences, King Fahd University of Petroleum and Minerals, Dhahran 31261, Saudi Arabia
2Department of Mathematics, Michigan State University, East Lansing, Michigan 48824, USA
2Department of Mathematics, Michigan State University, East Lansing, Michigan 48824, USA
DOI: 10.1007/s10801-006-0016-5
Abstract
A generic distance-regular graph is primitive of diameter at least two and valency at least three. We give a version of Derek Smith's famous theorem for reducing the classification of distance-regular graphs to that of primitive graphs. There are twelve cases-the generic case, four canonical imprimitive cases that reduce to the generic case, and seven exceptional cases. All distance-transitive graphs were previously known in six of the seven exceptional cases. We prove that the 6-cube is the only distance-transitive graph coming under the remaining exceptional case.
Pages: 195–207
Keywords: keywords imprimitive distance-transitive graph; imprimitive distance-regular graph
Full Text: PDF
References
1. M.R. Alfuraidan, “Imprimitive distance-transitive graphs,” Ph.D. Thesis, Michigan State University, March 2004.
2. M.R. Alfuraidan and J.I. Hall, “Imprimitive distance-transitive graphs with primitive core of diameter at least three,” in preparation.
3. N.L. Biggs and A. Gardiner, “The classification of distance transitive graphs,” unpublished manuscript, 1974.
4. J.T.M. van Bon and A.E. Brouwer, “The distance-regular antipodal covers of classical distance-regular graphs,” in: Colloq. Math. Soc. Janos Bolyai, Proc. Eger 1987, 1988, pp. 141-166.
5. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer, Berlin, 1989.
6. P.J. Cameron, Permutation Groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, Cambridge, 1999.
7. C.D. Godsil, R.A. Liebler, and C.E. “Praeger, Antipodal distance transitive covers of complete graphs,” Europ. J. Combin. 19 (1998), 455-478.
8. J. Hemmeter, “Halved graphs, Johnson and Hamming graphs,” Utilitas Math. 25 (1984), 115-118.
9. J. Hemmeter, “Distance-regular graphs and halved graphs,” Europ. J. Combin. 7 (1986), 119-129.
10. A.A. Ivanov, “Distance-transitive graphs and their classification,” in Investigations in the Algebraic Theory of Combinatorial Objects, I.A. Faradzev, A.A. Ivanov, M.H. Klin, and A.J. Woldar (Eds.), Kluwer, Dordrecht, 1994, pp. 283-378.
11. A.A. Ivanov, R.A. Liebler, T. Penttila, and C.E. Praeger, “Antipodal distance-transitive covers of complete bipartite graphs,” European J. Combin. 18 (1997), 11-33.
12. W.M. Kantor, “Classification of 2-transitive symmetric designs,” Graphs Combin. 1 (1985), 165-166.
13. M.W. Liebeck, “The affine permutation groups of rank three,” Proc. London Math. Soc. 54(3), (1987), 477-516.
14. D.H. Smith, “Primitive and imprimitive graphs, Quart,” J. Math. Oxford 22(2), (1971), 551-557.
2. M.R. Alfuraidan and J.I. Hall, “Imprimitive distance-transitive graphs with primitive core of diameter at least three,” in preparation.
3. N.L. Biggs and A. Gardiner, “The classification of distance transitive graphs,” unpublished manuscript, 1974.
4. J.T.M. van Bon and A.E. Brouwer, “The distance-regular antipodal covers of classical distance-regular graphs,” in: Colloq. Math. Soc. Janos Bolyai, Proc. Eger 1987, 1988, pp. 141-166.
5. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer, Berlin, 1989.
6. P.J. Cameron, Permutation Groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, Cambridge, 1999.
7. C.D. Godsil, R.A. Liebler, and C.E. “Praeger, Antipodal distance transitive covers of complete graphs,” Europ. J. Combin. 19 (1998), 455-478.
8. J. Hemmeter, “Halved graphs, Johnson and Hamming graphs,” Utilitas Math. 25 (1984), 115-118.
9. J. Hemmeter, “Distance-regular graphs and halved graphs,” Europ. J. Combin. 7 (1986), 119-129.
10. A.A. Ivanov, “Distance-transitive graphs and their classification,” in Investigations in the Algebraic Theory of Combinatorial Objects, I.A. Faradzev, A.A. Ivanov, M.H. Klin, and A.J. Woldar (Eds.), Kluwer, Dordrecht, 1994, pp. 283-378.
11. A.A. Ivanov, R.A. Liebler, T. Penttila, and C.E. Praeger, “Antipodal distance-transitive covers of complete bipartite graphs,” European J. Combin. 18 (1997), 11-33.
12. W.M. Kantor, “Classification of 2-transitive symmetric designs,” Graphs Combin. 1 (1985), 165-166.
13. M.W. Liebeck, “The affine permutation groups of rank three,” Proc. London Math. Soc. 54(3), (1987), 477-516.
14. D.H. Smith, “Primitive and imprimitive graphs, Quart,” J. Math. Oxford 22(2), (1971), 551-557.