ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 11 (2016) 49-58
Finite two-distance-transitive graphs of valency 6
Wei Jin *, Li Tan
School of Statistics, Jiangxi University of Finance and Economics, Nanchang, Jiangxi, 330013, P.R.China Research Center ofApplied Statistics, Jiangxi University ofFinance and Economics, Nanchang, Jiangxi, 330013, P.R.China
Received 20 December 2014, accepted 8 April 2015, published online 18 August 2015
A non-complete graph r is said to be (G, 2) -distance-transitive if, for i = 1, 2 and for any two vertex pairs (ui, vi) and (u2, v2) with dr(ui, vi) = dr(u2, v2) = i, there exists g G G such that (u1, v1)g = (u2, v2). This paper classifies the family of (G, 2)-distance-transitive graphs of valency 6 which are not (G, 2)-arc-transitive.
Keywords: 2-Distance-transitive graph, 2-arc-transitive graph, permutation group. Math. Subj. Class.: 05E18, 05B25
1 Introduction
In this paper, all graphs are finite, simple, connected and undirected. For a graph r, we use V(r) and Aut(r) to denote its vertex set and automorphism group, respectively. For the group theoretic terminology not defined here we refer the reader to [4, 8, 26]. Let u, v e V(r). Then the distance between u, v in r is denoted by dr (u, v). A non-complete graph r is said to be (G, 2)-distance-transitive, if for i = 1,2 and for any two vertex pairs (ui, vi) and (u2,v2) with dr(ui,vi) = dr(u2,v2) = i, there exists g e G such that (u1, v1)g = (u2, v2). An arc is an ordered pair of adjacent vertices. A vertex triple (u, v, w) with v adjacent to both u and w is called a 2-arc if u = w. The graph r is said to be (G, 2)-arc-transitive if G is transitive on both the set of arcs and the set of 2-arcs.
The first remarkable result about (G, 2)-arc-transitive graphs comes from Tutte [20,21], and since then, this family of graphs has been studied extensively, see [1, 12, 15, 16, 17, 23, 24]. By definition, every non-complete (G, 2)-arc-transitive graph is (G, 2)-distance-transitive. The converse is not necessarily true. If a (G, 2)-distance-transitive graph has
* Supported by the NNSF of China (11301230), NSF of Jiangxi (20142BAB211008) and Jiangxi Education Department Grant (GJJ14351).
E-mail addresses: jinwei@jxufe.edu.cn (Wei Jin), tltanli@126.com (Li Tan)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
50
Ars Math. Contemp. 11 (2016) 35-47
girth 3 (length of the shortest cycle is 3), then this graph is not (G, 2)-arc-transitive. Thus, the family of non-complete (G, 2)-arc-transitive graphs is properly contained in the family of (G, 2)-distance-transitive graphs. The graph in Figure 1 is the Kneser graph KG6,2 which is (G, 2)-distance-transitive but not (G, 2)-arc-transitive of valency 6 for G = Aut(KG6,2). Therefore the following problem naturally arises: characterize the family of (G, 2)-distance-transitive graphs. At the moment, Corr, Schneider and the first author are investigating such graphs, and they classified the family of (G, 2)-distance-transitive but not (G, 2)-arc-transitive graphs of valency at most 5 in [6]. Hence 6 is the next smallest valency for (G, 2)-distance-transitive graphs to investigate. Our main theorem gives a classification of such graphs.
Figure 1: Kneser graph KG6 2
Remark 1.1. Let r be a connected (G, 2)-distance-transitive graph. If r has girth at least 5, then for any two vertices u, v with dr (u, v) = 2, there exists a unique 2-arc between u and v. Hence r is (G, 2)-distance-transitive implies that it is (G, 2)-arc-transitive. If r has girth 4, then r can be (G, 2)-distance-transitive but not (G, 2)-arc-transitive. There are infinitely many such graphs. For instance, let r be the complement of the (2 x pk) - grid where p is a prime, and let M = Zk : Zpk-1, G = Z2 x M. Then r is (G, 2)-distance-transitive but not (G, 2)-arc-transitive of valency pk - 1 and girth 4. There are also infinitely many (G, 2)-distance-transitive graphs of girth 4 that are (G, 2)-arc-transitive, for example the complete bipartite graphs Km,m. If r has girth 3, then since r is non-complete, it follows that Gu is not 2-transitive on r(u), hence it is not (G, 2)-arc-transitive.
The line graph L(r) of a graph r has the set of edges of r as its vertex set, and two edges are adjacent in L(r) if and only if they have a common vertex in r. The line graph of a complete bipartite graph Km,n is called an (m x n) -grid. Let r be a connected graph. The complement graph r of r, is the graph with vertex V(r), and two vertices are adjacent in r if and only if they are not adjacent in r. The Hamming graph H(d, n) has vertex set Zn = Zn x Zn x • • • x Zn, and two vertices are adjacent if and only if they have exactly one different coordinate. We denote by Km[b] the complete multipartite graph with m parts, and each part has b vertices where m > 3, b > 2. Let p be a prime such that p = 1 (mod 4). Then, the Paley graph P(p) is the Cayley graph Cay(T, S) for the additive group T = Fp+ with S = {w2,w4,...,wp-1 = 1} and r2(1) = {w, w3,..., wp-2}, where w is a primitive element of Fp, and Aut(r) = Zp : Zp-i. In particular, Hamming graphs and Paley graphs are (G, 2)-distance-transitive for G = Aut(r), see [3, 13].
W. Jin and L. Tan: Finite two-distance-transitive graphs of valency 6
51
The diameter diam(T) of a graph r is the maximum distance occurring over all pairs of vertices. Let u G V(T) and i = 1,2,..., diam(T). We use r¿(u) to denote the set of vertices at distance i with vertex w in r. Sometimes, ^(u) is also denoted by r(w). Let Q be a set of cardinality n. Then the Kneser graph KG„jk is the graph with vertex set all k-subsets of Q, and two k-subsets are adjacent if and only if they are disjoint. The triangular graph T(n) is the graph with vertex set all 2-subsets of Q, and two 2-subsets are adjacent if and only if they share one common element. Thus KGn,2 = T(n). A subgraph X of r is an induced subgraph if two vertices of X are adjacent in X if and only if they are adjacent in r. When U C V(r), we use [U] to denote the subgraph of r induced by U.
Since complete graphs have diameter 1, they do not provide interesting examples. Our main theorem determines the family of non-complete (G, 2)-distance-transitive graphs of valency 6 which are not (G, 2)-arc-transitive.
Theorem 1.2. Let r be a connected non-complete (G, 2)-distance-transitive but not (G, 2)-arc-transitive graph of valency 6. Let u G V (r). Then one of the following holds.
(1)	r has girth 4, and (r, G) = ((2 x 7)-grid, S2 x M) where M is a 2-transitive but not 3-transitive subgroup of S7.
(2)	[r(w)] is connected, and r is isomorphic to one of: T(5), Paley graph P(13), K3[3] or K4[2].
(3)	[r(u)] is disconnected, and either
(3.1)	[r(u)] = 2K3, r = H(2,4), or |^(u)| = 18 and r is a line graph; or
(3.2)	[r(u)] = 3K2, r = KG6,2, or |^(u)| = 12, 24.
Remark 1.3. (1) There exist graphs r in Theorem 1.2 (3.1) such that |r2(u)| = 18. For instance the generalized hexagon of order (3,1) and the generalized dodecagon of order (3,1). These two graphs are locally isomorphic to 2K3 and |r2(u)| = 18. By [3, p.223], they are (G, 2)-distance-transitive for G = Aut(r), since they are non-complete and have girth 3, they are not (G, 2)-arc-transitive.
(2) There exist graphs r in Theorem 1.2 (3.2) such that |r2 (u)| = 12 and also exist graphs such that |r2(u)| = 24. For instance H(3,3) has valency 6, [r(u)] = 3K2 and |r2(u)| = 12; the halved foster graph has valency 6, [T(u)] ^ 3K2 and |r2(u)| = 24. By [3, p.223], these two graphs are (G, 2)-distance-transitive for G = Aut(r), since they are non-complete and have girth 3, they are not (G, 2)-arc-transitive.
2 Proof of Theorem 1.2
In this section, we will prove our main theorem by a series of lemmas. All graphs are non-complete graphs.
A graph r is said to be G-distance-transitive if G is transitive on the ordered pairs of vertices at any given distance. The study of finite G-distance-transitive graphs goes back to Higman's paper [10] in which "groups of maximal diameter" were introduced. These are permutation groups G which act distance-transitively on some graph. Then G-distance-transitive graphs have been studied extensively and a classification is almost done, see [2, 9, 11, 18, 19, 22, 25]. By definition, every non-complete G-distance-transitive graph is (G, 2)-distance-transitive.
The following remark gives an useful observation.
Remark 2.1. Let r be a (G, 2)-distance-transitive graph. Let u, w be two vertices such that dr(u, w) = 2.
52
Ars Math. Contemp. 11 (2016) 35-47
Suppose that |r3(u) n r(w)| = 0. Then since r is (G, 2)-distance-transitive, r has diameter 2 and so it is G-distance-transitive.
Suppose that |r3(u) n r(w)| = 1. Let (u0,... ,ui) be a path with dr(uo,Uj) = i where i = diam(r). Then for each j < diam(r) — 2, |r3(uj) n r(uj+2)| = 1. Note that,
rj+3(wo) n r(uj+2) C r3(uj) n r(uj+2), and so |r,-+3(uo) n r(uj+2)| = 1, hence r is also G-distance-transitive.
We use GU1] to denote the kernel of the Gu-action on r(u).
Lemma 2.2. Let r be a (G, 2)-distance-transitive graph. Let u, w G V(r) be such that dr(u, w) = 2. Let g G gU1] be with order a prime p. Suppose that |r3(u) n r(w)| < p. Then g is not trivial on r2 (u).
Proof. Suppose that g is trivial on r2(u). Let wi G r2(u). Since g G gU1] and g is trivial on r2(u), g fixes all the vertices in (r(u) U r2(u)) n r(wi) and g G Gwi. In particular, g fixes r3(u) n r(wi) setwise.
Since r is (G, 2)-distance-transitive and |r3(u) n r(w)| < p, |r3(u) n r(wi)| < p. Since the order of g is prime p and g fixes r3(u) n r(wi) setwise, it follows that g fixes all the vertices in r3(u) n r(wi). Thus g G gW!. Since wi is any vertex of r2(u), g fixes all the vertices of r3(u). For any v G r(u), r2(v) C r(u) U r2(u) U r3(u). Thus g G gV1] and fixes all the vertices of r2 (v).
Since r is (G, 2)-distance-transitive, for any z G r2(v), |r3(v) n r(z)| < p. Since g fixes all the vertices in (r(v) U r2(v)) n r(z), g fixes all the vertices in r3(v) n r(z). Thus g G Gi1]. In particular, g fixes all the vertices of r4 (u). Since r is connected, by induction, g fixes all the vertices of r, so g = 1, which is a contradiction. Thus g is not trivial on r2 (u).	□
Lemma 2.3. Let r be a (G, 2) -distance-transitive graph of valency 6. Let u, w G V(r) be such that dr(u, w) = 2. If r has girth 4 and |r(u) n r(w)| = 3, then r is (G, 2)-arc-transitive.
Proof. Suppose that r has girth 4 and |r(u) n r(w)| = 3. Let (u, v, w) be a 2-arc. Then dr(u, w) = 2 and |r2(u) n r(v)| = 5. Since r is (G, 2)-distance-transitive, there are 30 edges between r(u) andr2(u). Since |r(u)nr(w)| = 3 and |r(u)nr(w)| • |r2(u)| = 30, it follows that |r2(u)| = 10. Again since r is (G, 2)-distance-transitive, Gu is transitive on both r(u) and r2(u), so both |r(u)| and |r2(u)| divide |GU|, hence 30 divides |GU|. Thus 5 divides |Gu,v |, so Gu,v has an element g of order 5. Therefore either (g) is regular on r(u) \ {v} or is trivial on r(u) \ {v}. If (g) is regular on r(u) \ {v}, then Gu,v is transitive on r(u) \ {v}, so Gu is 2-transitive on r(u). Thus r is (G, 2)-arc-transitive.
Now suppose that g is trivial on r(u)\{v}. Then g G gU1]. Since |r(u) nr(w)| = 3, it follows that |r3(u) nr(w)| < 3 < 5. Thus by Lemma 2.2, g is not trivial on r2(u). Hence (g) has orbits of size 5 on r2(u). Since g fixes r2(u) nr(vi) setwise and |r2(u) nr(vi)| = 5, it follows that (g) is transitive on r2(u)nr(vi). Thus Gu,vi is transitive on r2(u)nr(vi), so r is (G, 2)-arc-transitive.	□
Lemma 2.4. ([6]) Let r = Km,m with m > 2. Then r is (G, 2)-distance-transitive if and only if it is (G, 2)-arc-transitive.
A permutation group G on a set Q is said to be 2-homogeneous, if G is transitive on the set of 2-subsets of Q.
W. Jin and L. Tan: Finite two-distance-transitive graphs of valency 6
53
Lemma 2.5. ([8, Theorem 9.4B]) Let G be a 2-homogeneous permutation group which is not 2-transitive of degree n. Then n = pe = 3 (mod 4) where p is a prime.
Lemma 2.6. Let r be a (G, 2)-distance-transitive but not (G, 2)-arc-transitive graph of valency 6. If r has girth 4, then (r, G) = ((2 x 7)-grid, S2 x M) where M is a 2-transitive but not 3-transitive subgroup of S7.
Proof. Suppose that r has girth 4. Let (u, v, w) be a 2-arc. Then dr(u, w) = 2, |r2(u) n r(v)| =5 and |r(u) n r(w)| > 2. Further there are 30 edges between r(u) and ^(u). Since r is (G, 2)-distance-transitive, |r(u) n r(w)| divides 30. Since 2 < |r(u) nr(w)| < 6, we have |r(u) n r(w) | = 2, 3, 5 or 6.
Suppose first that |r(u) n r(w)| = 2. Then since r has girth 4, each 2-arc of r lies in a unique 4-cycle. Thus, there is a 1-1 mapping between the unordered vertex pairs in r(u) and vertices in r2(u). Since Gu is transitive on r2(u), it follows that Gu is transitive on the set of unordered vertex pairs in r(u). Hence Gr(u) is 2-homogeneous on r(u). Further, since r is not (G, 2)-arc-transitive, Gr(u) is not 2-transitive on r(u). Thus by Lemma 2.5, the valency of r is pe = 3 (mod 4) where p is a prime, contradicting the fact that r has valency 6.
Next, if |r(u) n r(w)| = 3, then by Lemma 2.3, r is (G, 2)-arc-transitive, which is a contradiction.
Thirdly, suppose that |r(u) n r(w)| = 5. Then ^(u) n r(w)| < 1. It follows from Remark 2.1 that r is G-distance-transitive. By inspecting the graphs in [3, p. 222-223], r is isomorphic to (2 x 7)-grid. Noting that (2 x 7)-grid is (Aut(r), 2)-arc-transitive. Thus S2 < G < Aut(r) = S2 x S7. Let G = S2 x M where M < S7. Then Gu = Mu. Since r is (G, 2)-distance-transitive but not (G, 2)-arc-transitive, Mu is transitive but not 2-transitive on r(u). Thus M is a 2-transitive but not 3-transitive subgroup of S7.
Finally, if |r(u) n r(w) | = 6, then r = Ke,e, and by Lemma 2.4, r is (G, 2)-distance-transitive implies that it is (G, 2)-arc-transitive, which is a contradiction.	□
In a non-complete graph r, a 2-geodesic of r is a 2-arc (u0,u1, u2) such that dr (u0, u2) = 2. The graph r is said to be (G, 2)-geodesic-transitive, if G is transitive on both the set of arcs and the set of 2-geodesics. Hence, a non-complete G-arc-transitive graph is (G, 2)-geodesic-transitive if, for any arc (u, v), Gu,v is transitive on r2(w) n r(v). By definition, every (G, 2)-geodesic-transitive graph is (G, 2)-distance-transitive.
Suppose that r is a G-distance-transitive graph of valency k and diameter d. Then the cells of the distance partition with respect to vertex w are orbits of Gu, every vertex in r¿ (u) is adjacent to the same number of other vertices in ri_1 (u), say c¿. Similarly, every vertex in Fj(u) is adjacent to the same number of other vertices in ri+1(u), say 6¿. The notation (k, b1,..., bd_1; 1, c2,..., cd) is called the intersection array of r.
Lemma 2.7. Let r be a (G, 2)-distance-transitive but not (G, 2)-arc-transitive graph of valency 6. Let u G V(r). If [r(u)] is connected, then r is isomorphic to one of: T(5), Paley graph P(13), K3[3] or K^j.
Proof. Suppose that [T(u)] is connected. Let (u, v, w) be a 2-arc such that dr(u,w) = 2. Since r is (G, 2)-distance-transitive, Gu is transitive on r(u), so [r(u)] is a vertex-transitive graph. Let k be the valency of [r(u)]. Since [r(u)] is connected and |r(u) | = 6, it follows that k = 2,3,4, 5. Let r(u) = {v1, v2, v3, v4, v5, v6}.
If k = 5, then [r(u)] = K6, and so r = K7, contradicting the fact that r is non-complete.
54
Ars Math. Contemp. 11 (2016) 35-47
Suppose that k = 4. Then |r(u) n r(vi)| = 4, say r(u) n r(vi) = {v2, v3, v4, v5}. Since |r(u) n r(v6)| = 4 and v1,v6 are non-adjacent, it follows that r(u) n r(v6) = {v2, v3,v4,v5}. Thus [r(u)] has diameter 2, and {v1,v6} is a block. Since [r(u)] is vertex-transitive, [r(u)] = K3[2], and by [3, p.5] or [5], r = K4[2].
Suppose that k = 3. Then |r(u)nr(v1)| = 3, say r(u)nr(v1) = {v2, v3, v4}. Assume first that [r(u)] does not have triangles. Then every vertex of {v2, v3, v4} is adjacent to both v5 and v6. Thus [r(u)] = K3,3. Then by [3, p.5] or [5], r = K3[3]. Next, assume that [r(u)] has a triangle. Since [r(u)] is vertex-transitive, every vertex of r(u) lies in a triangle. Let (v1, v2, v3) be a triangle. Since [r(u)] is connected, v4 is adjacent to neither v2 nor v3. Thus v4 is adjacent to both v5 and v6. Since v4 lies in a triangle and {v5, v6} c r2(v1), it follows that v5, v6 are adjacent. Further, v2 is adjacent to one of {v5, v6}, say v5, and v3 is adjacent to the remaining vertex v6. Thus [r(u)] is isomorphic to the 3-prism, (v1, v2,v3) and (v4, v5, v6) are the two triangles, and {v1, v4}, {v2, v5} and {v3, v6} are edges. Since k = 3, it follows that |^(u) n r(v1)| = 2. Set ^(u) n r(v1) = {W1 ,W2}. Then r(v1) = {u, v2,v3, v4, w1, w2}. Since [r(v1)] is isomorphic to the 3-prism, it follows that v4 is adjacent to both w1 and w2, v2 is adjacent to one of {w1,w2}, say w1, and v3 is adjacent to w2. Thus r(v4) = {u, v1, v5, v6, w1, w2}. Since [r(v4)] is isomorphic to the 3-prism, it follows that w1 is adjacent to one of {v5, v6}, say v5. Thus {v1, v2, v4, v5} C r(u) n r(w1). Since w2 G r(w1), it follows that |r3(u) n r(w1)| < 1. Thus by Remark 2.1, r is G-distance-transitive.
Since {v1, v2, v4, v5} C r(u) n r(w1) and {w1} C r2(u) n r(w1), it follows that |r(u) n r(w1)| =4 or 5. Since r is (G, 2)-distance-transitive and |r2(u) n r(v1)| = 2, there are 12 edges between r(u) and r2(u). Thus |r(u) n r(w1)| divides 12, so |r(u) n r(w1)| = 4. Hence |r2(u)| = 3. Since Gu is transitive on r2(u), [r2(u)] is a vertex-transitive regular graph. Since w1,w2 are adjacent, [r2(u)] = C3. Therefore, |r3(u) n r(w1)| =0, r has diameter 2 and has 10 vertices. In particular, the intersection array of r is (6,2; 1,4). By inspecting the graphs in [3, p.222-223], r is T(5) (also known as the Johnson graph J(5, 2)).
If k = 2, then [r(u)] = C6. Let (v1,... ,v6) bea6-cycle. Then |r2(u) n r(v1)| = 3, and set r2(u) n r(v1) = {w1,w2,w3}. Then r(v1) = {u, v2, v5, w1, w2, w3}. Since [r(v1)] = C6 and (v2, u, v6) is a2-arc, it follows that v2 is adjacent to one of {w1, w2, w3}, say w1; v6 is adjacent to one of {w2, w3}, say w3; and w2 is adjacent to both w1 and w3. In particular, v2 is not adjacent to any of {w2, w3}, and v6 is not adjacent to any of {w1, w2}. Since |r2(u) n r(v2)| = 3, there exist w4, w5 in r2(u) that are adjacent to v2, and so r(v2) = {u, v1, v3, w1, w4, w5}. Noting that [r(v2)] = C6 and (w1, v1, u, v3) is a 3-arc, so v3 is adjacent to one of {w4, w5}, say w5, w1 is adjacent to w4, and w4, w5 are adjacent. Thus, {v1,v2,w2,w4} C (r(u) U r2(u)) n r(w1). Hence 2 < |r(u) n r(w1)| < 4 and |r2(u) n r(w1)| > 2. Since r is (G, 2)-distance-transitiveand |r2(u) n r(v1)| = 3, there are 18 edges between r(u) andr2(u). Since |r(u)nr(w1)| divides 18, |r(u)nr(w1)| = 2 or 3.
Suppose that |r(u) n r(w )| = 2. Then |^(u)| = 9. Since |r (u) n r(w1)| > 2, |r3(u) n r(w1)| < 2. If |r3(u) n r(w1)| < 1, then by Remark 2.1, r is G-distance-transitive. Inspecting the graphs in [3, p. 222-223], such a r does not exist. Hence |r3 (u) n r(w1)| = 2. Since r is (G, 2)-distance-transitive, both |r(u)| and |r2(u)| divide |Gu|, hence 18 divides |Gu|. Thus 3 divides |Gu,v |. Therefore Gu,v has an element g of order 3. Since |r(u) \ {v}| = 5, it follows that g is trivial on r(u) \ {v}, so g G G^]. Hence g fixes r2(u) n r(vj) setwise. By Lemma 2.2, g is not trivial on r2(u). Hence (g) has orbits of
W. Jin and L. Tan: Finite two-distance-transitive graphs of valency 6
55
size 3 on r2(u). Since g fixes r2(u) nr(vj) setwise and |r2 (u) nr(vj)| = 3, it follows that (g) is transitive on r2(u) n r(vj). Thus Gu,vi is transitive on r2(u) n r(vj). Therefore r is (G, 2)-geodesic-transitive. Then by [7, Corollary 1.4], r is either the Octahedron or the Icosahedron. However, these two graphs do not have valency 6, which is a contradiction.
Finally, suppose that |r(u) n r(wi)| = 3. Since there are 18 edges between r(u) and ^(u), and |^(u)| • |r(u) n r(wi)| = 18, |^(u)| = 6. Since |^(u) n r(wi)| > 2, |r3(u) n r(w1)| < 1. Thus by Remark 2.1, r is G-distance-transitive. Inspecting the graphs in [3, p. 222-223], r is the Paley graph P(13).	□
Lemma 2.8. Let r be a (G, 2)-distance-transitive graph of valency 6. Let u be a vertex of r. If [r(u)] = 2K3, then |r2 (u)| =9 or 18.
Proof. Suppose that [r(u)] = 2K3. Then each arc lies in a unique K4. Let r(u) = {v1,v2, v3, v4, v5, v6} such that (v1,v2,v3) and (v4,v5,v6) are two triangles. Then for each Vi, |r2(u)nr(v,)| = 3. Since [r(v1)] ^ 2K3, it follows that r2(u)nr(vi)nr(vj) = 0 for i, j € {1, 2, 3}. Thus |r2(u)| > 9.
On the other hand, since r is (G, 2)-distance-transitive and |r2(u) n r(v1)| = 3, there are 18 edges between r(u) and r2(u). Thus |r2(u)| divides 18, and so |r2(u)| = 9 or 18. □ If further |r2 (u) | = 9, then such a graph is unique.
Lemma 2.9. Let r be a (G, 2)-distance-transitive graph of valency 6. Let u be a vertex of r. Suppose that [r(u)] = 2K3 and |r2(u)| = 9. Then r = H(2,4)
Proof. Since [r(u)] = 2K3, each arc lies in a unique K4. Let r(u) = {v1, v2, v3, v4, v5, v6}. Let (v1,v2,v3) and (v4,v5,v6) be the two triangles of [r(u)]. Then for each Vj, |r2(u) n r(v,)| = 3. Since [r(v1)] = 2K3, it follows that r2(u) n r(v,) n r(vj) = 0 for i = j € {1, 2,3}. Since |^(u)| =9, r(u) = (^(u) n r(v1)) u (r2(u) n r(v2)) u (r2(u) n r(v3)). Setr2(u) nr(v1) = {w1,w2,w3}, r2(u) n r(v2) = {w4, w5,w6}, and r2(u) n r(v3) = {w7,w8,wg}. Since [r(v1)] = [r(v2)] = [r(v3)] = 2K3, it follows that (w1, w2, w3), (w4, w5, w6) and (w7, w8, w9) are three triangles.
Since r is (G, 2)-distance-transitive and |r2(u) n r(v1)| = 3, there are 18 edges between r(u) and r2(u). Since |r2(u)| = 9, it follows that for each wj, |r(u) n r(wj)| = 2. By the previous argument, w1 is not adjacent to any of {v2, v3}, so w1 is adjacent to one of {v4,v5,v6}, say v4. Then r(u) n r(w1) = {v1,v4}. As each arc lies in a unique K4 and (v1,w1 ,w2,w3) is a K4, it follows that v4 is not adjacent to any of {w2,w3}. Since |r(u) n r(v4)| = 3 and |r(vj) n r(v4)| = 2 for i = 1,2,3, V4 is adjacent to one of {w4,w5, w6}, say w4, and is adjacent to one of {w7, w8,w9}, say w7. Then r(v4) = {u,v5,v6,w1,w4,w7}. Since [r(v4)] = 2K3 and (u, v5,v6) is a triangle, it follows that (w1,w4,w7) is a triangle. Thus, r(w1) = {v1, v4, w2, w3, w4, w7}, and so r3(u) n r(w1) = 0. Since r is (G, 2)-distance-transitive, it follows that r is G-distance-transitive with diameter 2 and has 16 vertices. Thus by inspecting the graphs in [3, p. 222-223], r = H(2, 4).	□
Lemma 2.10. Let r be a (G, 2)-distance-transitive graph of valency 6. Let u be a vertex of r. If [r(u)] = 3K2, then |^(u)| = 8,12, or 24.
Proof. Suppose that [T(u)] = 3K2. Then each arc lies in a unique triangle. Let r(u) =
{v1, v2, v3, v4, v5, v6} be such that (v1, v2), (v3, v4), and (v5, v6) are three arcs. Then for
56
Ars Math. Contemp. 11 (2016) 35-47
each vi, ^ (u) nr(vi)| = 4. Since [r(vi)] = 3K2, it follows that ^(u) nr(vi) nr(v2) = 0. Thus |r2(u)| > 8.
Since r is (G, 2)-distance-transitive and |r2(u) n r(v1)| = 4, there are 24 edges between r(u) and r2 (u). Since |r2 (u) | divides 24, it follows that |r2 (u) | = 8, 12, or 24. □ If further |r2 (u) | = 8, then r is known.
Lemma 2.11. Let r be a (G, 2)-distance-transitive graph of valency 6. Let u be a vertex of r. Suppose that [T(u)] = 3K2 and |r2(u)| = 8. Then r = KG6,2
Proof. Since r is symmetric and [r(u)] = 3K2, each arc lies in a unique triangle. Set
r(u) = {v1, v2, v3, v4, v5,v6}. Let (v1,v2), (v3,v4) and (v5,v6) be three arcs. Then for each vi, ^ (u) nr(vi)| = 4. Since [r(vi)] = 3K2, it follows that r2(u) nr(vi) nr(v2) = 0. Since |r2(u)| = 8, r2(u) = (r2(u) n r(vi)) u (r2(u) n r(v2)). Setr2(u) n r(vi) = {w1, w2, w3, w4}, and r2(u) n r(v2) = {w5, w6, w7, w8}. Since [r(vi)] = [r(v2)] = 3K2, it follows that (w1, w2), (w3, w4), (w5, w6) and (w7, w8) are arcs.
Since r is (G, 2)-distance-transitive and |r2(u) n r(v1)| = 4, there are 24 edges between r(u) and r2(u). As |r2(u)| = 8, it follows that for each wi, |r(u) n r(wi)| = 3. By the previous argument, w1 is not adjacent to v2. Noting that r2(u) n r(vi) n r(v¿) = 0 for (i, j) = (1,2), (3,4), (5,6). Thus w1 is adjacent to one of {v3, v4}, say v3, and is also adjacent to one of {v5, v6}, say v5. Then r(u) n r(w1) = {v1, v3, v5}. Since each arc lies in a unique triangle and (v1, w1, w2) is a triangle, it follows that v3 is not adjacent to w2. By |r2(u) n r(v3)| =4 and |r(vi) n r(v3)| = 3 for i = 1,2, v3 is adjacent to one of {w3, w4}, say w3, and is also adjacent to two vertices of {w5, w6, w7, w8}, say w5, w7.
Then r(v3) = {u, v4, w1, w3, w5, w7}. Since [r(v3)] = 3K2 and (u,v4) is an arc, it follows that (w1,w5) and (w3,w7) are two arcs. Thus, {v1,v3,v5} U {w2,w5} C r(w1), and so |r3(u) n r(w1)| < 1. Since r is (G, 2)-distance-transitive, it follows from Remark 2.1 that r is G-distance-transitive. One part of the intersection array of r is (6,4,...; 1, 3,...). By inspecting the graphs in [3, p.221], r = KG6,2.	□
Lemma 2.12. Let r be an arc-transitive graph and let u be a vertex of r. Suppose that r(u) = U U W, where |U | = |W | = n and U n W = 0. Assume further that [U ] = [W ] = Kn. Let v1 € U. If |r(u) n r(v1) n W| < n - 2, then r is a line graph.
Proof. Suppose that |r(u) n r(v1) n W| < n - 2. Then [U] and [W] are the only two n-cliques of r(u). It follows from [14, Proposition 2.1] that r is a line graph.	□
Proof of Theorem 1.2. Let r be a connected non-complete (G, 2)-distance-transitive but not (G, 2)-arc-transitive graph of valency 6. If r has girth at least 5, then for any two vertices with distance 2, there exists a unique 2-arc between these two vertices. Thus r is (G, 2)-arc-transitive, which is a contradiction. Hence r has girth 3 or 4. If r has girth 4, then it follows from Lemma 2.6 that (r, G) = ((2 x 7)-grid, S2 x M) where M is a 2-transitive but not 3-transitive subgroup of S7, so that (1) holds.
Suppose that r has girth 3. Let (u, v, w) be a 2-arc such that dr (u, w) = 2. If [r(u)] is connected, then by Lemma 2.7, r is isomorphic to one of: T(5), Paley graph P(13), K3[3] or K4[2], (2) holds. If [r(u)] is disconnected, then Gu has blocks in r(u), and each block has cardinality 2 or 3. If each block has cardinality 3, then [r(u)] = 2K3; if each block has cardinality 2, then [r(u)] = 3K2. Suppose that [r(u)] = 2K3. Then by Lemma 2.8, |r2(u)| = 9 or 18. If |r2(u)| = 9, then by Lemma 2.9, r = H(2,4). If |r2(u)| = 18, then by Lemma 2.12, r is a line graph, (3.1) holds.
W. Jin and L. Tan: Finite two-distance-transitive graphs of valency 6
57
Finally, if [T(u)] ^ 3K2, then by Lemma 2.10, |r2(u)| = 8,12, or 24. In particular, if |r2(u)| = 8, then by Lemma 2.11, r = KGe,2, so that (3.2) holds.	□
References
[1]	B. Alspach, M. Conder, D. MaruSic and M. Y. Xu, A classification of 2-arc-transitive circulants, J. Algebraic Combin. 5 (1996), 83-86.
[2]	E. Bannai and T. Ito, On distance regular graphs with fixed valency, Graphs and Combin. 3
(1987),	95-109.
[3]	A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer Verlag, Berlin, Heidelberg, New York, 1989.
[4]	P. J. Cameron, Permutation Groups, volume 45 of London Mathematical Society Student Texts, Cambridge University Press, Cambridge, 1999.
[5]	A. M. Cohen, Local recognition of graphs, buildings, and related geometries, edited by W. M. Kantor, R. A. Liebler, S. E. Payne and E. E. Shult, In Finite Geometries, Buildings, and related Topics, Oxford Sci. Publ., New York, 1990, 85-94.
[6]	B. Corr, W. Jin and C. Schneider, Two-distance-transitive but not two-arc-transitive graphs, in preparation.
[7]	A. Devillers, W. Jin, C. H. Li and C. E. Praeger, Line graphs and geodesic transitivity, Ars Math. Contemp. 6 (2013), 13-20.
[8]	J. D. Dixon and B. Mortimer, Permutation groups, Springer, New York, 1996.
[9]	A. Gardiner and C. E. Praeger, Distance transitive graphs of valency six, Ars Combin. A 21 (1986), 195-210.
[10]	D. G. Higman, Intersection matrices for finite permutation groups, J. Algebra 6 (1967), 22-42.
[11]	A. A. Ivanov and A. V. Ivanov, Distance transitive graphs of valency k, 8 < k < 13, in Algebraic, Extremal and Metric Combinatorics, in 1986, Cambridge Univ. Press, Cambridge,
(1988),	112-145.
[12]	A. A. Ivanov and C. E. Praeger, On finite affine 2-arc transitive graphs. European J. Combin. 14 (1993), 421-444.
[13]	W. Jin, A. Devillers, C. H. Li and C. E. Praeger, On geodesic transitive graphs, Discrete Math., 338 (2015), 168-173.
[14]	W. Jin, W. J. Liu and S. J. Xu, Line graphs and 2-geodesic transitive graphs, submitted.
[15]	C. H. Li and J. M. Pan, Finite 2-arc-transitive abelian Cayley graphs, European J. Combin. 29 (2008), 148-158.
[16]	D. MaruSic, On 2-arc-transitivity of Cayley graphs, J. Combin. Theory Ser. B 87 (2003), 162196.
[17]	C. E. Praeger, On a reduction theorem for finite, bipartite, 2-arc transitive graphs, Australas. J. Combin. 7 (1993) 21-36.
[18]	C. E. Praeger, J. Saxl and K. Yokohama, Distance transitive graphs and finite simple groups, Proc. London Math. Soc. (3)55 (1987), 1-21.
[19]	D. H. Smith, Distance transitive graphs of valency four, J. London Math. Soc. (2)8 (1974), 377-384.
[20]	W. T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (1947), 459-474.
[21]	W. T. Tutte, On the symmetry of cubic graphs, Canad. J. Math. 11 (1959), 621-624.
58
Ars Math. Contemp. 11 (2016) 35-47
[22]	J. Van Bon, Affine distance transitive groups, Proc. London Math. Soc., (3)67 (1993), 1-52.
[23]	R. Weiss, s-Arc transitive graphs, Algebraic Metheods in Graph Theory I, II, (Szeged, 1978), Colloq. Math. Soc. Janos. Bolyai vol.25, North Holland, Amsterdam, 1978, 827-847.
[24]	R. Weiss, The non-existence of 8-transitive graphs, Combinatorica 1 (1981), 309-311.
[25]	R. Weiss, Distance transitive graphs and generalized polygons, Arch. Math. 45 (1985), 186192.
[26]	H. Wielandt, Finite Permutation Groups, New York: Academic Press, 1964.