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}} .

Key words： 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