Abstract
A complete classification is given of 2-distance-transitive circulants, which shows that a 2-distance-transitive circulant is a cycle, a Paley graph of prime order, a regular complete multipartite graph, or a regular complete bipartite graph of order twice an odd integer minus a 1-factor.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
In this paper, all graphs are finite, simple, and undirected. An ordered pair of adjacent vertices is called an arc. A graph \({\varGamma }\) is called arc-transitive if all arcs are equivalent under automorphisms of the graph. For a graph \({\varGamma }\) and two vertices u and v, the distance between u and v in \({\varGamma }\) is denoted by d(u, v), which is the smallest length of paths between u and v. The diameter\(\mathrm{diam}({\varGamma })\) of \({\varGamma }\) is the maximum distance occurring over all pairs of vertices. An arc-transitive graph \({\varGamma }\) is said to be 2-distance-transitive if \({\varGamma }\) is not complete, and any two vertex pairs of vertices \((u_1,v_1)\) and \((u_2,v_2)\) with \(d(u_1,v_1)=d(u_2,v_2)=2\) are equivalent under automorphisms.
A 2-arc is a triple of distinct vertices (u, v, w) such that v is adjacent to both u and w. A regular graph is called 2-arc-transitive if all 2-arcs are equivalent under automorphisms. A 2-arc-transitive graph is obviously 2-distance-transitive.
The concept of 2-distance-transitive graph generalizes the concepts of distance-transitive graph and 2-arc-transitive graph. Both distance-transitive graphs and 2-arc-transitive graphs have been extensively studied, see [3, 15]. The investigation of 2-distance-transitive graphs was initiated recently, see [4,5,6].
A vertex-transitive graph with n vertices is called a circulant if it has an automorphism of order n which acts freely on the set of vertices. Alspach et al. [1] classified 2-arc-transitive circulants; Miklavič and Potočnik [13] classified distance-regular circulants; Kovács [10] and Li [11] gave a characterization of arc-transitive circulants, see Theorem 2.1. The purpose of this paper is to give a complete classification of 2-distance-transitive circulants, stated in the following main theorem.
Theorem 1.1
The class of 2-distance-transitive graphs consists of cycles, Paley graphs of prime order, regular complete multipartite graphs, and regular complete bipartite graphs of order twice an odd integer minus a 1-factor.
By definition, a 2-distance-transitive circulant is an arc-transitive circulant. Thus, to prove Theorem 1.1, we only need to determine which of the arc-transitive circulants described in [10, 11] are 2-distance-transitive. However, this is unexpectedly nontrivial (see Lemmas 2.3–2.10), which motivates some interesting problems that we explain below.
For a finite group G and a subset S of G such that \(1\notin S\) and \(S=S^{-1}\), the Cayley graph\(\mathrm{Cay}(G,S)\) of G with respect to S is the graph with vertex set G and edge set \(\{\{g,sg\} \,|\,g\in G,s\in S\}\). It is known that a graph \({\varGamma }\) is a Cayley graph of G if and only if \({\varGamma }\) has an automorphism group which is isomorphic to G and regular on the vertex set, see [2, Lemma 16.3] and [17]. For a Cayley graph \({\varGamma }=\mathrm{Cay}(G,S)\), if G is a normal subgroup of \(\mathrm{Aut}{\varGamma }\), then \({\varGamma }\) is called a normal Cayley graph. The study of normal Cayley graphs was initiated by Xu [18] and has been done under various additional conditions, see [7, 16]. A circulant is thus a Cayley graph of a cyclic group, and if further it is a normal Cayley graph of a cyclic group, then it is called a normal circulant. Many interesting examples of arc-transitive graphs and 2-arc-transitive graphs are constructed as normal Cayley graphs, due to the fact that the arc-transitivity and 2-arc-transitivity of a graph are equivalent to the local-transitivity and local-2-transitivity, respectively. The status for 2-distance-transitive graphs is, however, different. To our best knowledge, the known examples of 2-distance-transitive graphs are either distance-transitive or 2-arc-transitive. For instance, 2-distance-transitive normal circulants are cycles and Paley graphs by Theorem 1.1, which are distance-transitive. The following is a curious question.
Question 1.2
Is there a normal Cayley graph which is 2-distance-transitive, but neither distance-transitive nor 2-arc-transitive?
Another interesting problem is to characterize 2-distance-transitive Cayley graphs of certain special classes of groups, such as abelian groups and metacyclic groups.
2 Proof
We first introduce the classification of arc-transitive circulants given in [10, 11], which we need to prove Theorem 1.1.
Let \({\varGamma }=(V,E)\) be a connected graph with vertex set V and edge set E. Its complement graph\(\overline{{\varGamma }}\) is the graph with vertex V such that two vertices are adjacent in \(\overline{{\varGamma }}\) if and only if they are not adjacent in \({\varGamma }\). Let \({\varGamma }_1=(V_1,E_1)\) and \({\varGamma }_2=(V_2,E_2)\) be two graphs. Then \({\varGamma }={\varGamma }_1[{\varGamma }_2]\) denotes the lexicographic product of \({\varGamma }_1\) and \({\varGamma }_2\), where the vertex set of \({\varGamma }\) is \(V_1\times V_2\), and two vertices \((u_1,u_2)\) and \((v_1,v_2)\) are adjacent in \({\varGamma }\) if either \(u_1\) and \(v_1\) are adjacent in \({\varGamma }_1\), or \(u_1=v_1\) and \(u_2,v_2\) are adjacent in \({\varGamma }_2\).
For a positive integer b, let \(\mathrm{K}_b\) be the complete graph with b vertices. For a graph \({\varGamma }\), the graph consisting of b vertex disjoint copies of \({\varGamma }\) is denoted by \(b{\varGamma }\), and \({\varGamma }[\overline{\mathrm{K}_b}]-b{\varGamma }\) is the graph whose vertex set is the same as \({\varGamma }[\overline{\mathrm{K}_b}]\) and edge set equals the edge set of \({\varGamma }[\overline{\mathrm{K}_b}]\) minus the edge set of \(b{\varGamma }\).
Theorem 2.1
[11, Theorem 1.3] Let \({\varGamma }\) be a connected arc-transitive circulant of order n which is not a complete graph. Then either
-
(1)
\({\varGamma }\) is a normal circulant, or
-
(2)
there exists an arc-transitive circulant \({\varSigma }\) of order m such that \( mb=n\) with \(b,m>1\) and
$$\begin{aligned} {\varGamma }=\left\{ \begin{array}{ll} {\varSigma }\big [\overline{\mathrm{K}_b}\big ], \ \ or \\ {\varSigma }\big [\overline{\mathrm{K}_b}\big ]-b{\varSigma }, \text{ where } (m,b)=1. \end{array}\right. \end{aligned}$$
Our proof of Theorem 1.1 is to analyze which graphs satisfying Theorem 2.1 are 2-distance-transitive. We now describe all examples of 2-distance-transitive circulants, which consist of cycles and the following three families:
Example 2.2
-
(1)
Let \({\varGamma }=\mathrm{K}_{m[b]}\) be a complete multipartite graph which has m parts of size b. Clearly, \(\mathrm{K}_{m[b]}=\mathrm{K}_m[\overline{\mathrm{K}_b}]\). Then \(\mathrm{Aut}{\varGamma }=\mathrm{S}_b\wr \mathrm{S}_m\) is 2-distance-transitive on \({\varGamma }\) and has a cyclic subgroup which is regular on the vertex set. Thus \({\varGamma }\) is a 2-distance-transitive circulant.
-
(2)
Let \({\varGamma }=\mathrm{K}_{b,b}-b\mathrm{K}_2\) where b is an odd integer, namely, a complete bipartite graph minus a 1-factor. Then \({\varGamma }\) is of valency \(b-1\) and of diameter 3, and \(\mathrm{Aut}{\varGamma }=\mathrm{S}_b\times \mathrm{S}_2\) is distance-transitive and 2-arc-transitive. It follows that \({\varGamma }\) is a 2-distance-transitive circulant.
-
(3)
Let \(q=p^e\) be a prime power such that \(q\equiv 1 \pmod {4}\). Let \({\mathbb {F}}_q\) be the finite field of order q. Then the Paley graph\(\mathsf{P}(q)\) is the graph with vertex set \({\mathbb {F}}_q\), and two distinct vertices u, v are adjacent if and only if \(u-v\) is a nonzero square in \({\mathbb {F}}_q\). The congruence condition on q implies that \(-1\) is a square in \({\mathbb {F}}_q\), and hence \(\mathsf{P}(q)\) is an undirected graph. This family of graphs was first defined by Paley in 1933, see [14]. Note that the field \({\mathbb {F}}_q\) has \((q-1)/2\) elements which are nonzero squares, so \(\mathsf{P}(q)\) has valency \((q-1)/2\). Moreover, \(\mathsf{P}(q)\) is a Cayley graph for the additive group \(G={\mathbb {F}}_{q}^+\cong \mathbb {Z}_{p}^e\). Let w be a primitive element of \({\mathbb {F}}_q\). Then \(S=\{w^2,w^4,\ldots ,w^{q-1}=1\}\) is the set of nonzero squares of \({\mathbb {F}}_q\), and \(\mathsf{P}(q)=\mathrm{Cay}(G,S)\). If \(q=p\) is a prime, then \(\mathsf{P}(p)\) is a circulant of prime order. By [12], \(\mathrm{Aut}\mathsf{P}(p) ={\mathbb {F}}_p^+:\langle w^2\rangle \). This implies that \(\mathsf{P}(p)\) is a 2-distance-transitive normal circulant.
Proof of Theorem 1.1
By Example 2.2, cycles, regular complete multipartite graphs, regular complete bipartite graphs of order twice an odd integer minus a 1-factor, and Paley graphs of prime order are all distance-transitive and so 2-distance-transitive.
Conversely, let \({\varGamma }=\mathrm{Cay}(G,S)\) be a connected 2-distance-transitive circulant, and \(G\cong \mathbb {Z}_n\). Then \({\varGamma }\) is arc-transitive, and so \({\varGamma }\) satisfies Theorem 2.1. If \({\varGamma }\) is of valency 2, then \({\varGamma }\cong \mathrm{C}_n\). Assume that \({\varGamma }\) has valency at least 3. Since \({\varGamma }\) is arc-transitive, either \({\varGamma }\) is a normal circulant, or \({\varGamma }\) satisfies part (2) of Theorem 2.1. We shall treat these two cases in two subsections, respectively. In Sect. 2.1, we prove that if \({\varGamma }\) is a normal circulant, then \({\varGamma }\) is a Paley graph of prime order, stated in Lemma 2.8. In Sect. 2.2, we deal with nonnormal circulants and show that, if \({\varGamma }\) is not a normal circulant, then \({\varGamma }\) is a regular complete multipartite graph, or a regular complete bipartite graph of order twice an odd integer minus a 1-factor. \(\square \)
We now introduce a few notations which we will use later. For a graph \({\varGamma }\) and a vertex v, we denote by \({\varGamma }_i(v)\) the i-th neighborhood of v in \({\varGamma }\), that is, the set of vertices which are at distance i from v. A sequence of vertices \(v_0,v_1,\dots ,v_s\) is called an s-geodesic if \(\{v_i,v_{i+1}\}\) is an edge for all \(0\leqslant i\leqslant s-1\) and \(d(v_0,v_s)=s\). We sometimes need to consider distances of the same pair of vertices in different graphs, so let \(d_{\varGamma }(u,v)\) denote the distance of u and v in the graph \({\varGamma }\).
2.1 2-Distance-transitive normal circulants
Consider the cyclic group
Let \({\varGamma }=\mathrm{Cay}(G,S)\) be a connected 2-distance-transitive circulant of valency \(k\geqslant 3\). Then \(G=\langle S\rangle \). Assume further that \({\varGamma }\) is a normal circulant. Let \(A=\mathrm{Aut}{\varGamma }\), and let u be the vertex of \({\varGamma }\) corresponding to the identity of the group G. Then \({\varGamma }(u)=S\) and \(A=G{:}A_u\). By [9, Lemma 2.1], we have
Moreover, as \(\mathrm{Aut}(G)\) is abelian and \(A_u=\mathrm{Aut}(G,S)\) is transitive and faithful on S, it implies that \(A_u\) is regular on S, and
We establish a series of lemmas to prove that \({\varGamma }\) is a Paley graph.
Lemma 2.3
\({\varGamma }\) has girth 3.
Proof
Suppose that the girth of \({\varGamma }\) is greater than 4. Then, for each pair of vertices \(\theta ,\theta '\) with distance \(d(\theta ,\theta ')=2\), there is a unique 2-arc between \(\theta \) and \(\theta '\). Hence \({\varGamma }\) being 2-distance-transitive implies that it is 2-arc-transitive. By the classification given in [1, Theorem 1.1], the graph \({\varGamma }\) has girth 4, which is a contradiction.
Assume that \({\varGamma }\) has girth 4. Then, for any vertex \(v\in {\varGamma }(u)=S\), we have \(|{\varGamma }_2(u)\cap {\varGamma }(v)|=k-1\). Thus there are \(k(k-1)\) edges between \({\varGamma }(u)\) and \({\varGamma }_2(u)\). Since \(|A_u|=k\) and A is 2-distance-transitive on \({\varGamma }\), we conclude that \(A_u\) acts transitively on \({\varGamma }_2(u)\), and the size \(|{\varGamma }_2(u)|\) is a divisor of \(|A_u|=k\). Let \(w\in {\varGamma }_2(u)\cap {\varGamma }(v)\). Then \(|S\cap {\varGamma }(w)|\leqslant |{\varGamma }(w)|=k\). Note that \(|S\cap {\varGamma }(w)|\cdot |{\varGamma }_2(u)|=k(k-1)\). Hence \(|S\cap {\varGamma }(w)|=k-1\) and \(k=|{\varGamma }_2(u)|=|S|\). It follows that \(|{\varGamma }_3(u)\cap {\varGamma }(w)|+|{\varGamma }_2(u)\cap {\varGamma }(w)|=1\). Set \({\varGamma }(u)=\{v=v_1,\ldots ,v_k\}\) and \({\varGamma }_2(u)=\{w=w_1,\ldots ,w_k\}\). Let \({\varGamma }_2(u)\cap {\varGamma }(v)=\{w_1,\ldots ,w_{k-1}\}\) and \({\varGamma }(u)\cap {\varGamma }(w)=\{v_1,\ldots ,v_{k-1}\}\).
Assume that \(|{\varGamma }_3(u)\cap {\varGamma }(w)|=0\). Then \(|{\varGamma }_2(u)\cap {\varGamma }(w)|=1\). Since \({\varGamma }\) is 2-distance-transitive, the stabilizer \(A_u\) is transitive on \({\varGamma }_2(u)\), so the induced subgraph \([{\varGamma }_2(u)]\cong (k/2)\mathrm{K}_2\). As \({\varGamma }\) has girth 4, it follows that \([{\varGamma }_2(u)\cap {\varGamma }(v)]\) is an empty graph, and so \(w_1\) is adjacent to \(w_k\). Thus \([\{w_2,\ldots ,w_{k-1}\}]\cong (k/2-1)\mathrm{K}_2\). However, \(\{w_2,\ldots ,w_{k-1}\}\subset {\varGamma }_2(u)\cap {\varGamma }(v)\), contradicting the fact that \([{\varGamma }_2(u)\cap {\varGamma }(v)]\) is an empty graph. Therefore, \(|{\varGamma }_3(u)\cap {\varGamma }(w)|=1\), say \({\varGamma }_3(u)\cap {\varGamma }(w)=\{z\}\).
By the transitivity of \(A_u\) on the set \({\varGamma }(u)\), we have \(|{\varGamma }_2(u)\cap {\varGamma }(v_k)|=|{\varGamma }_2(u)\cap {\varGamma }(v_1)|=k-1\). Then \({\varGamma }_2(u)\cap {\varGamma }(v_k)=\{w_2,\dots ,w_k\}\) since \(v_k\) and \(w_1\) are not adjacent in \({\varGamma }\). Note that \((u,w),(v,z),(v_k,z)\) are all vertex pairs of distance 2 and \({\varGamma }\) is 2-distance-transitive. We have \(|{\varGamma }(u)\cap {\varGamma }(w)|\), \(|{\varGamma }(v)\cap {\varGamma }(z)|\) and \(|{\varGamma }(v_k)\cap {\varGamma }(z)|\) are all equal to \(k-1\). Hence \({\varGamma }(v)\cap {\varGamma }(z)={\varGamma }(v)\cap {\varGamma }_2(u)\) and \({\varGamma }(v_k)\cap {\varGamma }(z)={\varGamma }(v_k)\cap {\varGamma }_2(u)\). Thus \({\varGamma }(z)={\varGamma }_2(u)\) and \({\varGamma }_3(u)=\{z\}\), so \({\varGamma }\) has diameter 3 and is distance-transitive. Therefore, \(\{u\}\cup {\varGamma }_3(u)\) is a block of imprimitivity of \(\mathrm{Aut}{\varGamma }\) on the vertex set V, and \({\varGamma }\cong \mathrm{K}_{k+1,k+1}-(k+1)\mathrm{K}_2\). It is clear that \(\mathrm{K}_{k+1,k+1}-(k+1)\mathrm{K}_2\) is not a normal circulant, which is a contradiction. Hence the girth of \({\varGamma }\) is 3. \(\square \)
Lemma 2.4
The order \(|G|=n\) is odd.
Proof
Suppose that \(|G|=n\) is an even integer. Since \(G=\langle S\rangle \) and all elements of S have the same order, it follows that S consists of generators of G. Without loss of generality, we assume that \(g\in S\). By Lemma 2.3, \({\varGamma }\) has girth 3. Then there is \(g^i\in S\) such that \((g,g^i)\) is an arc of \({\varGamma }\). This implies that \(g^{i-1}=g^ig^{-1}\) belongs to set S. Since \({\varGamma }\) is a normal circulant, each element in S is a generator of G. This means that \(1,i-1,i\) are all relatively prime to n. This contradicts the fact that n is an even number. \(\square \)
Lemma 2.5
The second neighborhood \({\varGamma }_2(u)\) consists of generators of G.
Proof
Suppose that \({\varGamma }_2(u)\) contains an element which is not a generator of G. Then |G| is not a prime. Since \(A_u=\mathrm{Aut}(G,S)\) is transitive on \({\varGamma }_2(u)\), none of the elements in \({\varGamma }_2(u)\) is a generator.
As \(\langle S\rangle =G\) and all elements of S are conjugate in \(\mathrm{Aut}(G)\), we may assume that \(g\in S\). By Lemma 2.4, the order |G| is an odd integer. Thus \(g^2\) is a generator, and \(g^2\notin {\varGamma }_2(u)\). Since \(g^2\in {\varGamma }(u)\cup {\varGamma }_2(u)\), \(g^2\in S={\varGamma }(u)\). Assume that \(g^r\in S\) where \(r\leqslant n-3\). Then \(g^{r+1}=g^rg\in {\varGamma }(u)\cup {\varGamma }_2(u)\). Thus either \(g^{r+1}\) is a generator of G and \(g^{r+1}\in S\), or \(g^{r+1}\) is not a generator and \(g^{r+1}\in {\varGamma }_2(u)\). Similarly, we have \(g^{r+2}=g^rg^2\in {\varGamma }(u)\cup {\varGamma }_2(u)\). Therefore, either \(g^{r+2}\) is a generator of G and \(g^{r+2}\in S\), or \(g^{r+2}\) is not a generator and \(g^{r+2}\in {\varGamma }_2(u)\).
Let p be the smallest prime divisor of \(n=|G|\). Then \(g,g^2,\dots ,g^{p-1}\in S\), and \(g^p\in {\varGamma }_2(u)\). Suppose that G is not a p-group. Let q be the second smallest prime divisor of n. By the deduction above, we have \(g^\lambda \in S\) for any \(1\leqslant \lambda \leqslant q-1\) with \((\lambda ,p)=1\). Noting that p is coprime to at least one of \(q-2\) and \(q-1\). If p and \(q-2\) are coprime, then \(g^{q-2}\in S\), so \(g^q=g^{q-2}g^2\in {\varGamma }_2(u)\), as \(g^2\in S\); if p and \(q-1\) are coprime, then \(g^{q-1}\in S\), so \(g^q=g^{q-1}g\in {\varGamma }_2(u)\), as \(g\in S\). Thus, \(g^{q}\) is in \( {\varGamma }_2(u)\). However \({\varGamma }\) is 2-distance-transitive and normal, which means that all elements of \({\varGamma }_2(u)\) have the same order. This contradicts the fact that \(o(g^{p})\ne o(g^{q})\) and \(g^{p}, g^{q}\in {\varGamma }_2(u)\). Thus G is a p-group.
Suppose that \(|G|=p^r\). If \(r\geqslant 3\), then by a similar argument as the previous paragraph, we have \(g^\lambda \in S\) for any \(1\leqslant \lambda \leqslant p^{r}-1\) with \((\lambda ,p)=1\). Hence \(g^{p},g^{p^2}\in {\varGamma }_2(u)\). This is impossible since \(o(g^{p})\ne o(g^{p^2})\) and all elements of \({\varGamma }_2(u)\) have the same order.
Therefore, we get \(n=p^2\). Furthermore, \(S=\{g^\lambda |1\leqslant \lambda \leqslant p^2-1,(p,\lambda )=1\}\) and \({\varGamma }_2(u)=\{g^{\mu p}|1\leqslant \mu \leqslant p-1\}\). Thus \({\varGamma }\cong \mathrm{K}_{p[p]}\).
Note that \(\mathrm{K}_{p[p]}\) is not normal. We have that \({\varGamma }_2(u)\) has no nongenerators of G. This means \({\varGamma }_2(u)\) consists of generators of G. \(\square \)
Let
the second neighborhood of the vertex u (corresponding to the identity of G).
Lemma 2.6
The stabilizer \(A_u\) is regular on R, and \(|R|=|S|\) divides \(p-1\) for each prime divisor p of |G|.
Proof
Since A is 2-distance-transitive on \({\varGamma }\), \(A_u\) is transitive on \(R={\varGamma }_2(u)\). As \(A_u=\mathrm{Aut}(G,S)\) is abelian and R consists of generators of G, \(A_u\) is faithful on R. Thus \(A_u\) is regular on \(R={\varGamma }_2(u)\), and so \(|R|=|A_u|=|S|\).
Let \(n=p_1^{t_1}p_2^{t_2}\dots p_{\ell }^{t_{\ell }}\), where \(p_1<p_2<\dots <p_\ell \) are distinct primes. Let \(G=\langle x_1\rangle \times \dots \times \langle x_\ell \rangle \), where \(o(x_i)=p_i^{t_i}\) for \(1\leqslant i\leqslant \ell \) and \(g=x_1\dots x_\ell \). Then
Set
where \(1\leqslant j\leqslant \ell \). We claim that \(A_u\cap B_j=\{1\}\) and \(A_u\cong A_uB_j/B_j\lesssim \mathbb {Z}_{p_j-1}\).
Assume that \(A_u\cap B_j\ne \{1\}\). Then there exists \(\sigma \in A_u\cap B_j\) such that \(\sigma \ne 1\). Hence \(g^\sigma =(x_1\dots x_\ell )^\sigma =(x_1\dots x_{j-1})^\sigma x_j (x_{j+1} \dots x_\ell )^\sigma \), and \(g^\sigma g^{-1} \ne 1\) is not a generator of G. Observing that g and \(g^\sigma \) are in S, we have \(g^\sigma g^{-1}\in S\cup R\), which contradicts the fact that all elements in S and R are generators of G. Hence \(A_u\cap B_j=\{1\}\) and
If \(p_j\) divides \(|A_u|\), then there exists \(\sigma \in A_u\) such that \(o(\sigma )=p_j\). Furthermore, \(x_j^\sigma =x_j^{\lambda p_j+1}\ne x_j\) for some integer \(\lambda \). Thus \(g^\sigma g^{-1}\in \langle x_1\rangle \times \dots \times \langle x_{j-1}\rangle \times \langle x_j^{p_j}\rangle \times \langle x_{j+1}\rangle \times \dots \langle x_{\ell }\rangle \) is not a generator of G. This contradicts the fact that \(g^\sigma g^{-1}\in S\cup R\). Therefore, \(A_u\lesssim \mathbb {Z}_{p_j-1}\) for \(1\leqslant j\leqslant \ell \). Noting that \(A_u\) acts regularly on S, \(|S|=|A_u|\). Hence |S| divides \(p_i-1\) for \(1\leqslant i\leqslant \ell \). \(\square \)
By virtue of Lemma 2.6, we can assume that
where \(\lambda \) is coprime to n. Let \(g^\mu \) be an element of R and \(\tau \) be an automorphism of G such that \(g^\tau =g^\mu \). Then \((g^\mu )^\tau =(g^\tau )^\mu =g^{\mu ^2}\). Let \(k=|S|=|A_u|\). We have
Let
Then \({\varSigma }\) and \({\varGamma }\) are isomorphic. (Two graphs are isomorphic if there exists a bijection between their vertex sets which preserves the adjacency and the nonadjacency.)
Lemma 2.7
Let \(x,y\in G\). Then \(\mathrm{d }_{\varGamma }(x,y)=2\) if and only if \(\mathrm{d }_{\varGamma }(xy^{-1},u)=2\), and the following conditions are equivalent:
-
(i)
\(xy^{-1}\in R\);
-
(ii)
\(\mathrm{d }_{\varSigma }(x,y)=1\);
-
(iii)
\(\mathrm{d }_{\varGamma }(x,y)=\mathrm{d }_{\varGamma }(xy^{-1},u)=2\).
Proof
For any \(y\in G\), let \(\sigma _{{y}^{-1}}\) be the right translation by \(y^{-1}\). Then \(\sigma _{{y}^{-1}}\) is an automorphism of \({\varGamma }\) since \({\varGamma }\) is a Cayley graph of G. Thus for any \(x\in G\), we have
Noting that \(R={\varGamma }_2(u)={\varSigma }(u)\), we have \(xy^{-1}\in R\) if and only if \(d_{\varGamma }(xy^{-1},u)=d_{\varGamma }(x,y)=2\). By the same argument, we also have \(xy^{-1}\in R\) if and only if \(d_{\varSigma }(xy^{-1},u)=d_{\varSigma }(x,y)=1\). \(\square \)
For two sets \(B_1,B_2\), we use \(B_1\sqcup B_2\) to denote \(B_1\cup B_2\) when \(B_1\cap B_2=\emptyset \). We denote \({\varGamma }_{\geqslant i}(u)={\varGamma }_{i}(u)\cup {\varGamma }_{ i+1}(u)\cup \cdots \cup {\varGamma }_{\mathrm{diam}({\varGamma })}(u)\).
Lemma 2.8
The graph \({\varGamma }\) is a Paley graph \(\mathsf{P}(p)\), where \(p\equiv 1\)\((\mathsf{mod\ }4)\) is prime.
Proof
By Lemma 2.5, \({\varGamma }_2(u)=R\) contains generators of G. If the diameter of \({\varGamma }\) is 2, then all the elements in \(G\setminus \{u\}\) are generators of G, and so n is an odd prime p. By Lemma 2.6, \(|S|=|R|\), so \(|S|=|R|=(p-1)/2\). Thus S is either the set of square elements or the set of nonsquare elements of \(G\setminus \{u\}\), and \({\varGamma }\) is the Paley graph \(\mathsf{P}(p)\), see also [8, Lemma 2.2].
In the remainder, we suppose that \({\varGamma }\) has diameter at least 3. Let (u, z, v, w) be a 3-geodesic of \({\varGamma }\). We set \(k=|S|=|R|\), \(a_1=|{\varGamma }(z)\cap S|\), \(b_1=|{\varGamma }(z)\cap R|\) and \(c_2=|{\varGamma }(v)\cap S|\). Let N be the number of edges in \({\varGamma }\) with one end in S and the other end in R. Then
Hence \(b_1=c_2\).
Note that all S, R, and \(R^\tau \) are orbits of \(A_u\). We will argue in two cases.
Case 1\(R^\tau \ne S\).
Since \(\Sigma _2(u)=R^\tau \) and \(R^\tau \ne S\), it follows that \(S\subseteq \Sigma _{\geqslant 3}(u)\). Thus, for each \(y\in R\) and \(x\in S\), \(d_\Sigma (x,y)\ne 1\), and it follows from Lemma 2.7 that \(d_{\varGamma }(x,y)\ne 2\).
Let \(w\in R^\tau \). Then there exist vertices \(z\in S\) and \(v\in R\), such that (u, v, w) and (u, z, v) are 2-geodesics in \(\Sigma \) and \({\varGamma }\), respectively. Hence, by Lemma 2.7, \(d_{\varGamma }(w,v)=2\) (Fig. 1).
Since \({\varGamma }\) is 2-distance-transitive, there exists \(\eta \in A_v\) such that \(u^\eta =w\). Thus
Since \({\varGamma }(v)\cap {\varGamma }(w)\subseteq R\cup {\varGamma }_3(u)\), we have
For any \(x\in S\cap {\varGamma }(z)\), (v, z, x) is a 2-arc. Since \(d_{\varGamma }(v,x)\ne 2\), \(d_{\varGamma }(v,x)=1\) and \(x\in {\varGamma }(v)\). Thus
and \(a_1+1\leqslant b_1\). Consider the valency of the vertex z, we have
By inequalities (1) and (3), \(k=2b_1\), so (2) can be modified into
By the same deduction, for any \(y\in {\varGamma }(z)\cap R\), we have
Similarly, for each \(x\in {\varGamma }(z)\cap S\subset {\varGamma }(v)\cap S\),
Equalities (5) and (6) indicate that for each \(x\in {\varGamma }(z)\setminus \{u\}\), \({\varGamma }(x)\cap S\subset \{z\}\sqcup ({\varGamma }(z)\cap S)\).
Let \(z'\in S\setminus (\{z\}\cup {\varGamma }(z))\). Then \(d_{\varGamma }(z,z')=2\). There is an automorphism \(\eta \in A\) such that \(z^\eta =u\) and \((z')^\eta =v\). Let \((z,x,z')\) be a 2-arc in \({\varGamma }\). Then \(z'\in {\varGamma }(x)\cap S\) and \(x\in {\varGamma }(z)\). Thus \(x=u\) and
Hence \(k=2\). This contradicts the assumption that \({\varGamma }\) has valency at least 3.
Case 2 \(R^\tau =S.\)
Since \(R^\tau =S\), it follows that \({\varGamma }_{\geqslant 3}(u)=\Sigma _{\geqslant 3}(u)\). For each \(x\in R\) and \(y\in \Sigma _{\geqslant 3}(u)\), we have \(d_\Sigma (x,y)\ne 1\). This implies \(d_{\varGamma }(x,y)\ne 2\). Thus \({\varGamma }_{\geqslant 3}(u)={\varGamma }_{3}(u)\) and \(\mathrm{diam}({\varGamma })=3\) (Fig. 2).
Let \(w\in {\varGamma }_3(u)\). Then there exist \(z\in S, v\in R\) such that (u, z, v, w) is a 3-geodesic. Let
Then \(k=1+a_1+b_1=a_2+b_2+c_2=a_3+c_3\).
Let p be the smallest prime factor of n, and let \(N'\) be the number of edges in \({\varGamma }\) with one end in R and the other end in \({\varGamma }_3(u)\). Then
Hence \(n\leqslant k^2+k+1\). By Lemma 2.6, k is a divisor of \(p-1\), and thus \(k+1<p+1\). Then \(n\leqslant k^2+k+1=k(k+1)+1<(p-1)(p+1)+1=p^2\), and so n is a prime. This implies that w is also a generator of G and \(|w^{A_u}|=|A_u|=k\). Furthermore,
This means
For any \(x\in {\varGamma }(w)\cap {\varGamma }_3(u)\), (v, w, x) is a 2-arc. Since \(d_{\varGamma }(v,x)\ne 2\), we have \(d_{\varGamma }(v,x)=1\) and \(x\in {\varGamma }(v)\). Thus
and
By inequalities (7) and (8), we have
For any \(x\in S\setminus \{z\}\), (z, u, x) is a 2-arc in \({\varGamma }\), and \(d_{\varGamma }(z,x)\leqslant 2\). Thus
Note that \({\varGamma }_2(z)\cap S=\Sigma (z)\cap S\) and
for some \(v'\in R\) where the graph isomorphism \(\tau \) is defined in the paragraph before Lemma 2.7. We have
Hence \(k=1+a_1+b_1=1+a_1+a_2\), and
For any \(x\in {\varGamma }(z)\cap S\), (v, z, x) is a 2-arc in \({\varGamma }\). Thus we have \(d_{\varGamma }(x,v)\leqslant 2\). Then
and
Thus \(b_1=k-(1+a_1)\geqslant k-2b_1=b_2\). By inequality (9),
This is a contradiction.
Therefore, \({\varGamma }\) is of diameter 2, and is a Paley graph as observed above. \(\square \)
2.2 2-Distance-transitive nonnormal circulants
Let \({\varGamma }=(V,E)\) be an arc-transitive circulant which is not a normal circulant. By Theorem 2.1, there exists an arc-transitive circulant \({\varSigma }\) of order m such that \( mb=n\), and
We next determine which of these graphs are 2-distance-transitive.
The vertex set V of \({\varGamma }\) is partitioned into m parts of size b, and thus we may label the vertices as
such that
are blocks for \(\mathrm{Aut}{\varGamma }\). Let \({\mathcal {B}}=\{B_1,B_2,\dots ,B_m\}\), the corresponding block system for \(\mathrm{Aut}{\varGamma }\) acting on V. The quotient graph\({\varGamma }_{\mathcal {B}}\) is the graph with vertex set \(V_{\mathcal {B}}={\mathcal {B}}\) such that two vertices \(B_1,B_2\in {\mathcal {B}}\) are adjacent if and only if there exist \(u_1\in B_1\) and \(u_2\in B_2\) which are adjacent in \({\varGamma }\). Then \({\varGamma }_{\mathcal {B}}\cong {\varSigma }\), and each element \(g\in \mathrm{Aut}{\varGamma }\) naturally induces a permutation \(\overline{g}\) on set \({\mathcal {B}}\) which is an automorphism of the graph \({\varGamma }_{\mathcal {B}}\).
Lemma 2.9
Let u be an arbitrary vertex in \({\varGamma }\). Then, except for the case \({\varGamma }=\Sigma [\overline{\mathrm{K}_2}]-2\Sigma \), the subset \(\{u\}\cup {\varGamma }_2(u)\subset V\) is a block of size b.
Proof
It is clear that \(B_1\) is a block of size b for \(\mathrm{Aut}{\varGamma }\). Without loss of generality, set \(u=v_{1,1}\), since \({\varGamma }\) is vertex-transitive. Thus, we only need to show that \(B_1=\{u\}\cup {\varGamma }_2(u)\).
Let \(w=v_{1,2}\in B_1\). We have \(d_{\varGamma }(u,w)\geqslant 2\) since the induced subgraph \([B_1]\cong \overline{\mathrm{K}_b}\). Suppose that \(B_1,B_2\) are two vertices of \({\varGamma }_{{\mathcal {B}}}\) which are adjacent. If \({\varGamma }={\varSigma }[\overline{\mathrm{K}_b}]\), then \((u ,v_{2,1},w)\) is a 2-geodesic of \({\varGamma }\). If \({\varGamma }={\varSigma }[\overline{\mathrm{K}_b}]-b{\varSigma }\), where \(b\geqslant 3\), then \((u,v_{2,3},w)\) is a 2-geodesic of \({\varGamma }\). Thus in either case, \(w\in {\varGamma }_2(u)\). By the same deduction, for any \(w'\in B_1\setminus \{u\}\), we have \(w'\in {\varGamma }_2(u)\). Hence \(B_1\subseteq \{u\}\cup {\varGamma }_2(u)\).
Let \(A=\mathrm{Aut}{\varGamma }\) and \(A_u\) be the stabilizer of vertex u. Since \({\varGamma }\) is 2-distance-transitive and \(B_1\) is a block of V for A, we have \(w^{A_u}={\varGamma }_2(u)\subseteq B_1\). Thus \(\{u\}\cup {\varGamma }_2(u)= B_1\), and it is a block of size b on V for A. \(\square \)
Lemma 2.10
Let \({\varGamma }\) be a 2-distance-transitive circulant which is not a normal circulant. Then \({\varGamma }=\mathrm{K}_{m[b]}\) or \(\mathrm{K}_{b,b}-b\mathrm{K}_2\).
Proof
Assume first that \(m=2\). Since \({\varGamma }\) is of valency at least 3 by our assumption, either \(b\geqslant 3\) and \({\varGamma }= \mathrm{K}_{b,b}\), or \(b\geqslant 5\) and \({\varGamma }=\mathrm{K}_2[\overline{\mathrm{K}_b}]-b\mathrm{K}_2= \mathrm{K}_{b,b}-b\mathrm{K}_2\). We next consider the case where \(m\geqslant 3\).
Assume that \({\varGamma }={\varSigma }[\overline{\mathrm{K}}_b]\) with \(m\geqslant 3\). Let \(u=v_{1,1}\in B_1\). By Lemma 2.9, \(\{u\}\cup {\varGamma }_2(u)= B_1\) is a block for \(A=\mathrm{Aut}{\varGamma }\). Thus there is no vertex \(w\in V\setminus B_1\) at distance 2 with u in \({\varGamma }\). It follows that \({\varSigma }\) is a complete graph, and so \({\varGamma }\cong {\varSigma }[\overline{\mathrm{K}_b}]\cong \mathrm{K}_{m[b]}\).
Now, let \({\varGamma }= {\varSigma }[\overline{\mathrm{K}_b}]-b{\varSigma }\) with \(m\geqslant 3\) and \(b\geqslant 3\). Again, by Lemma 2.9, \(\{u\}\cup {\varGamma }_2(u)= B_1\) is a block for \(A=\mathrm{Aut}{\varGamma }\). Similarly, there is no vertex \(w\in V\setminus B_1\) at distance 2 with u in \({\varGamma }\), and \({\varSigma }\) is a complete graph. Therefore, \((u,v_{2,2},v_{3,1})\) is a 2-geodesic in \({\varGamma }\). This contradicts the fact that \(v_{3,1}\notin B_1=\{u\}\cup {\varGamma }_2(u)\).
Finally, assume that \({\varGamma }= {\varSigma }[\overline{\mathrm{K}_2}]-2{\varSigma }\) with \(m\geqslant 3\). According to Lemma 2.1, m is relatively prime to b. Hence m is an odd integer. If \({\varSigma }\) is a complete graph, then \({\varGamma }=\mathrm{K}_{m[2]}-2\mathrm{K}_m\). Note that \(\mathrm{K}_{m[2]}-2\mathrm{K}_m\) is isomorphic to \(\mathrm{K}_{2[m]}-m\mathrm{K}_2\). We have \({\varGamma }\cong \mathrm{K}_{2[m]}-m\mathrm{K}_2\). If \({\varSigma }\) is not a complete graph, then it is clear that the quotient graph \({\varGamma }_{{\mathcal {B}}}\) is also 2-distance-transitive. By the argument above we have \({\varGamma }_{{\mathcal {B}}}\) is isomorphic to \(\mathrm{C}_m\), \(\mathsf{P}(p)\), or \(\mathrm{K}_{m'[b']}\). When \(p=5\), the Paley graph \(\mathsf{P}(5)\) is isomorphic to \(\mathrm{C}_5\). If \({\varGamma }_{{\mathcal {B}}}\cong \mathrm{C}_m\) then \(\Gamma \cong \mathrm{C}_{2m}\) is normal, a contradiction. If \({\varGamma }_{{\mathcal {B}}}\cong \mathsf{P}(p)\) for \(p>5\), there is a triangle in \({\varGamma }_{{\mathcal {B}}}\). If \({\varGamma }_{{\mathcal {B}}} \cong \mathrm{K}_{m'[b']}\), then there exists a triangle in \({\varGamma }_{{\mathcal {B}}}\) too. In either case, let \((B_1,B_2,B_3)\) be a triangle in \({\varGamma }_{{\mathcal {B}}}\) and \((B_1,B_2,B_4)\) be a 2-geodesic in \({\varGamma }_{{\mathcal {B}}}\). Since \({\varGamma }= {\varSigma }[\overline{\mathrm{K}_2}]-2{\varSigma }\), it follows that the vertex \(v_{2,2}\) is adjacent to \(v_{1,1}\), \(v_{3,1}\), and \(v_{4,1}\), and the vertex \(v_{1,1}\) is not adjacent to \(v_{3,1}\) and \(v_{4,1}\). Hence \((v_{1,1},v_{2,2},v_{3,1})\) and \((v_{1,1},v_{2,2},v_{4,1})\) are two 2-geodesics in \({\varGamma }\). Thus there exists an automorphism \(\sigma \in \mathrm{Aut}{\varGamma }\) such that \(v_{1,1}^\sigma =v_{1,1}\) and \(v_{3,1}^\sigma =v_{4,1}\). This is impossible since \(\sigma \) induces an automorphism of \({\varGamma }_{{\mathcal {B}}}\) and \(1=d_{{\varGamma }_{{\mathcal {B}}}}(B_1,B_3)\ne d_{{\varGamma }_{{\mathcal {B}}}}(B_1,B_4)=2\). \(\square \)
References
Alspach, B., Conder, M., Marušič, D., Xu, M.Y.: A classification of 2-arc transitive circulants. J. Algebraic Combin. 5, 83–86 (1996)
Biggs, N.: Algebraic Graph Theory. Cambridge Mathematical Library, 2nd edn. Cambridge University Press, Cambridge (1993)
Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin, Heidelberg, New York (1989)
Corr, B., Jin, W., Schneider, C.: Finite two-distance-transitive graphs. J. Graph Theory (2017). https://doi.org/10.1002/jgt.22112
Devillers, A., Giudici, M., Li, C.H., Praeger, C.E.: Locally \(s\)-distance transitive graphs. J. Graph Theory 69(2), 176–197 (2012)
Devillers, A., Giudici, M., Li, C.H., Praeger, C.E.: Locally \(s\)-distance transitive graphs and pairwise transitive designs. J. Combin. Theory Ser. A 120, 1855–1870 (2013)
Devillers, A., Jin, W., Li, C.H., Praeger, C.E.: On normal 2-geodesic transitive Cayley graphs. J. Algebraic Combin. 39, 903–918 (2014)
Devillers, A., Jin, W., Li, C.H., Praeger, C.E.: Finite 2-geodesic transitive graphs of prime valency. J. Graph Theory 80, 18–27 (2015)
Godsil, C.D.: On the full automorphism group of a graph. Combinatorica 1, 243–256 (1981)
Kovács, I.: Classifying arc-transitive circulants. J. Algebraic Combin. 20, 353–358 (2004)
Li, C.H.: Permutation groups with a cyclic regular subgroup and arc transitive circulants. J. Algebraic Combin. 21, 131–136 (2005)
Lim, T.K., Praeger, C.E.: On generalized Paley graphs and their automorphism groups. Michigan Math. J. 58, 293–308 (2009)
Miklavič, Š., Potočnik, P.: Distance-regular circulants. European J. Combin. 24(7), 777–784 (2003)
Paley, R.E.A.C.: On orthogonal matrices. J. Math. Phys. 12, 311–320 (1933)
Praeger, C.E.: An O’Nan Scott theorem for finite quasiprimitive permutation groups and an application to 2-arc transitive graphs. J. Lond. Math. Soc. 47(2), 227–239 (1993)
Praeger, C.E.: Finite normal edge-transitive Cayley graphs. Bull. Aust. Math. Soc. 60, 207–220 (1999)
Sabidussi, G.: Vertex-transitive graphs. Monatsh. Math. 68, 426–438 (1964)
Xu, M.Y.: Automorphism groups and isomorphisms of Cayley digraphs. Discrete Math. 182, 309–319 (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by NSF of China (11661039,11231008,11771200,11561027) and NSF of Jiangxi (20171BAB201010, 20171BCB23046, GJJ170321).
Rights and permissions
About this article
Cite this article
Chen, J., Jin, W. & Li, C.H. On 2-distance-transitive circulants. J Algebr Comb 49, 179–191 (2019). https://doi.org/10.1007/s10801-018-0825-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10801-018-0825-3