Pentavalent vertex-transitive diameter two graphs

Abstract

We classify the family of pentavalent vertex-transitive graphs \Gamma with diameter 2. Suppose that the automorphism group of \Gamma is transitive on the set of ordered distance 2 vertex pairs. Then we show that either \Gamma is distance-transitive or \Gamma is one of \overline{{{\displaystyle C}}_{\mathrm{8}}},{{\displaystyle \mathrm{K}}}_{\mathrm{5}}{{\displaystyle \square \mathrm{K}}}_{\mathrm{2}},{{\displaystyle C}}_{\mathrm{5}}[{{\displaystyle \mathrm{K}}}_{\mathrm{2}}],\overline{{{\displaystyle \mathrm{2}C}}_{\mathrm{4}}},\mathrm{or}{{\displaystyle \mathrm{K}}}_{\mathrm{3}}{{\displaystyle \square \mathrm{K}}}_{\mathrm{4}} .

Keywords

vertex-transitive graph / diameter / automorphism group

References

[1] Amarra C, Giudici M, Praeger C E. Quotient-complete arc-transitive graphs. European J Combin, 2012, 33: 1857–1881

[2] Amarra C, Giudici M, Praeger C E. Symmetric diameter two graphs with affine-type vertex-quasiprimitive automorphism group. Des Codes Cryptogr, 2013, 68: 127–139

[3] Brouwer A E, Cohen A M, Neumaier A. Distance-Regular Graphs. Berlin: Springer-Verlag, 1989

[4] Cameron P J. Permutation Groups. London Math Soc Stud Texts, Vol 45. Cambridge: Cambridge Univ Press, 1999

[5] Cheng Y, Oxley J. On weakly symmetric graphs of order twice a prime. J Combin Theory Ser B, 1987, 42: 196–211

[6] Devillers A. A classi_cation of _nite partial linear spaces with a rank 3 automorphism group of grid type. European J Combin, 2008, 29: 268–272

[7] Devillers A, Giudici M, Li C H, Pearce G, Praeger C E. On imprimitive rank 3 permutation groups. J Lond Math Soc, 2011, 84: 649–669

[8] Devillers A, Jin W, Li C H, Praeger C E. Local 2-geodesic transitivity and clique graphs. J Combin Theory Ser A, 2013, 120: 500–508

[9] Devillers A, Jin W, Li C H, Praeger C E. On normal 2-geodesic transitive Cayley graphs. J Algebraic Combin, 2014, 39: 903–918

[10] 0. Dixon J D, Mortimer B. Permutation Groups. New York: Springer, 1996

[11] Gorenstein D. Finite Simple Groups|An Introduction to Their Classi_cation. New York: Plenum Press, 1982

[12] Hestenes M D, Higman D G. Rank 3 groups and strongly regular graphs. SIAM-AMS Proc, 1971, 4: 141–159

[13] Jin W. Vertex-transitive graphs of diameter 2. Preprint

[14] Kov_acs I. Classifying arc-transitive circulants. J Algebraic Combin, 2004, 20: 353–358

[15] Kwak J H, Oh J M. One-regular normal Cayley graphs on dihedral groups of valency 4 or 6 with cyclic vertex stabilizer. Acta Math Sin (Engl Ser), 2006, 22: 1305–1320

[16] Li C H. Permutation groups with a cyclic regular subgroup and arc transitive circulants. J Algebraic Combin, 2005, 21: 131–136

[17] Li C H, Pan J M. Finite 2-arc-transitive abelian Cayley graphs. European J Combin, 2008, 29: 148–158

[18] Mckay B, Praeger C E. Vertex-transitive graphs which are not Cayley graphs. J Aust Math Soc (A), 1994, 56: 53–63

[19] Morris J, Praeger C E, Spiga P. Strongly regular edge-transitive graphs. Ars Math Contemp, 2009, 2: 137–155

[20] Wang R J, Xu M Y. A classi_cation of symmetric graphs of order 3p:J Combin Theory Ser B, 1993, 58: 197–216

[21] Wielandt H. Finite Permutation Groups. New York: Academic Press, 1964

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg