Des Codes Crypt (2006) 41: 185–193 DOI 10.1007/s10623-006-9008-7

Distance-transitive dihedrants Štefko Miklaviˇc · Primož Potoˇcnik

Received: 21 March 2006 / Revised: 1 June 2006 / Accepted: 8 June 2006 / Published online: 14 September 2006 © Springer Science+Business Media, LLC 2006

Abstract The main result of this article is a classification of distance-transitive Cayley graphs on dihedral groups. We show that a Cayley graph X on a dihedral group is distance-transitive if and only if X is isomorphic to one of the following graphs: the complete graph K2n ; a complete multipartite graph Kt×m with t anticliques of size m, where tm is even; the complete bipartite graph without 1-factor Kn,n − nK2 ; the cycle C2n ; the incidence or the non-incidence graph of the projective geometry PGd−1 (d, q), d ≥ 2; the incidence or the non-incidence graph of a symmetric design on 11 vertices. Keywords Cayley graph · Distance-regular graph · Distance-transitive graph · Dihedrant · Dihedral group · Difference set AMS Classifications

05C25 · 05E20 · 05E30

1 Introduction A connected finite graph X is distance-transitive if for every i ≥ 0, the automorphism group Aut(X) acts transitively on the set of ordered pairs of vertices at distance i apart. In particular, every distance-transitive graph is vertex-transitive. In this paper, we determine which graphs from a special, but important class of vertex-transitive graphs (namely, the Cayley graphs on dihedral groups, also called dihedrants) are distance-transitive.

Communicated by C. E. Praeger. S. Miklaviˇc (B) Department of Mathematics and Computer Science, Faculty of Education, University of Primorska, Cankarjeva 5, 6000 Koper, Slovenia e-mail: [email protected] P. Potoˇcnik Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia e-mail: [email protected]

186

Des Codes Crypt (2006) 41: 185–193

We start by presenting four obvious families of distance-transitive Cayley graphs, which will be called trivial for the purpose of this article. These are: complete graphs Kn (with diameter 1), complete multipartite graphs Kt×m with t anticliques of size m (with diameter 2), complete bipartite graphs without a 1-factor Km,m − mK2 (with diameter 3), and cycles Cn (with diameter n/2). In can be easily checked that these trivial distance-transitive graphs are Cayley graphs on dihedral groups if and only if their order is even. Further examples of distance-transitive dihedrants arise in the context of symmetric designs. If ν, k, and µ are positive integers satisfying ν ≥ k ≥ 2, then a symmetric (ν, k, µ)-design is an ordered pair (P , B) where P is a point set of size ν and B is a collection of ν k-subsets of P such that two distinct points in P are simultaneously contained in exactly µ elements of B. (This then implies that the intersection of any two distinct elements of B has size µ.) The elements of B are usually referred to as blocks of the design. Classical examples of symmetric designs are the designs PGd−1 (d, q), d ≥ 2, q a prime power, with the point-set and block-set being the sets of points and hyperplanes of the finite projective geometry PG(d, q), respectively. The second family of symmetric designs relevant for our investigation is the family of Paley-Hadamard designs PalHad(q), q a prime congruent 3 modulo 4, with point-set being the finite field Fq of order q, and block-set being the set of cosets i + {x2 : x ∈ Fq \{0}}, i ∈ Fq . The incidence graph of a symmetric (ν, k, µ)-design (B, P ) is the bipartite graph with the vertex set B ∪ P and with v ∈ P adjacent to B ∈ B whenever v ∈ B. Note that the incidence graph is regular of valency k, and any two vertices at distance 2 apart have exactly µ common neighbours. Similarly, the non-incidence graph of (B, P ) is the bipartite graph with the same vertex set, but with v ∈ P adjacent to B ∈ B whenever v  ∈ B. We can now formulate the main result of this paper. Theorem 1.1 A Cayley graph on the dihedral group of order 2n is distance-transitive if and only if it is isomorphic to one of the following graphs: (1) a trivial distance-transitive graph of order 2n, (2) the incidence or the non-incidence graph of a symmetric design PGd−1 (d, q), where

−1 , d ≥ 2, q is a prime power, and n = qq−1 (3) the incidence or the non-incidence graph of the symmetric Paley-Hadamard design PalHad(11). d

The proof of Theorem 1.1 is based on a recent partial classification of distanceregular dihedrants, obtained in [6]. This result, along with related material, is presented in Sect. 2. We also use Kantor’s classification of 2-transitive symmetric designs [4], which relies on the classification of finite simple groups. Theorem 1.1 is proved in Sect. 3.

2 Preliminaries A difference set in a group G is a subset D of G, such that the number of pairs (r1 , r2 ) ∈ D × D satisfying r2 r1−1 = g is constant for all g ∈ G \{1}. Difference sets can also be defined in the language of group algebras. We shall abuse the notation and use the same
symbol to denote a subset S of a group G and the corresponding element S = a∈S a of the group algebra ZG. For S ⊆ G we let S(−1) denote the set

Des Codes Crypt (2006) 41: 185–193

187

{s−1 | s ∈ S} (as well as the corresponding element of ZG). The notion of a difference set can then be defined as follows: Let ν, k and µ be non-negative integers, let G be a group of order ν, and let D be a k-subset of G. Then D is a (ν, k, µ)-difference set if and only if DD(−1) = (k − µ)1G + µG. If |D| ∈ {|G|, |G| − 1, 1, 0}, then D is trivial, otherwise it is non-trivial. For a vertex x of a graph X and for an integer i, we let Si (x) denote the set of vertices which are at distance i from x. A connected graph X of diameter d is said to be distance-regular whenever, for all integers h, i, j, (0 ≤ h, i, j ≤ d) and all pairs of vertices (x, y) at distance h apart, the number phij = |Si (x) ∩ Sj (y)|

(1)

is independent of the choice of x and y. (Note that every distance-transitive graph is distance-regular, but not vice-versa.) The constants phij (0 ≤ h, i, j ≤ d) are known as the intersection numbers of X, and the array {b0 , b1 , . . . , bd−1 ; c1 , c2 , . . . , cd }, where ci = pi1,i−1 and bi = pi1,i+1 , is called the intersection array of X (for additional background on distance-regular graphs, see [2]). For a finite group G and a subset S ⊆ G\{1} satisfying S = S(−1) , let Cay(G; S) denote the Cayley graph on G relative to the symbol S whose vertex set is G and the adjacency relation is given by g ∼ h ⇔ h−1 g ∈ S. Throughout this article, the following notation will be used. For a positive integer n, Dn will denote the dihedral group with 2n elements, generated by an element ρ of order n and an involution τ satisfying the relation τρτ = ρ −1 . For subsets R, T ⊆ Zn we let ρ R = {ρ i | i ∈ R} and ρ T τ = {ρ i τ | i ∈ T}. For a subset A ⊆ Zn and an element i ∈ Zn , we let i + A = {i + a | a ∈ A} and iA = {ia | a ∈ A}. Finally, by Dih (n; R, T) we denote the Cayley graph Cay(Dn ; ρ R ∪ ρ T τ ). The following partial classification on distance-regular dihedrants was proved in [6]. Theorem 2.1 A Cayley graph X on the dihedral group of order 2n is distance-regular if and only if one of the following holds: (1) X is a trivial distance-regular graph of order 2n, (2) X ∼ = Dih (n; ∅, T), where T is a non-trivial difference set in the group Zn . (3) n is even and X ∼ = Dih (n; R, T), where R and T are non-empty subsets of 1 + 2Zn such that ρ −1+R ∪ρ −1+T τ is a non-trivial difference set in the dihedral group ρ 2 , τ  of order n. If either (2) or (3) holds, then X is bipartite, non-antipodal, and has diameter 3. Note that this result is not completely satisfactory since it relies on a classification of difference sets in cyclic and dihedral groups. Even though cyclic difference sets were extensively studied and many examples are known, their complete classification seems to be beyond current state of knowledge. On the other hand, it is an old, not yet answered question whether any non-trivial difference sets in dihedral groups exist at all. Hence it is still open whether any distance-regular dihedrants arise from case (3). Moreover, not every non-trivial difference set in a dihedral group would necessarily give rise to a distance-regular dihedrant since it might not be imbeddable into a larger dihedral group as indicated in case (3). It is therefore very likely that the graphs arising in case (2) are the only non-trivial distance-regular dihedrants. In case of distance-transitive dihedrants, we overcome this difficulty by showing that every non-trivial distance-transitive dihedrant arises (as an incidence graph) from a

188

Des Codes Crypt (2006) 41: 185–193

doubly transitive symmetric design containing a point-regular cyclic or dihedral group (see Sect. 3.3 for details). Theorem 1.1 then follows from Kantor’s classification of doubly transitive symmetric designs [4]. Let us mention that the smallest non-trivial distance-regular dihedrant, which is not distance-transitive, is the incidence graph of the symmetric design PalHad(19). It can be represented as Dih (19; ∅, {1, 4, 5, 6, 7, 9, 11, 16, 17}). According to [5], an abstract group H is called a DT-group if every distanceregular Cayley graph of H is distance-transitive. Therefore D19 is the smallest dihedral group which is not a DT-group. Let us finish this section with a short discussion of distance-regular dihedrants arising from cyclic difference sets. The study of cyclic difference sets (that is, difference sets in cyclic groups) dates back to 1938 when Singer [9] defined the concept and described an infinite family of cyclic difference sets. His family is in fact a subfamily of cyclic −1 q ( q q−1−1 , qq−1 , q−1−1 )-difference sets giving rise to the classical symmetric designs PGd−1 (d, q) (see Sect. 3.2 for details). Let us mention that the smallest two non-trivial distance-regular dihedrants arise as the incidence and the non-incidence graphs of symmetric design PG1 (2, 2), also known as the Fano plane. The corresponding distance-regular dihedrants Dih (7; ∅, {1, 2, 4}) and Dih (7; ∅, {0, 3, 5, 6}) are isomorphic to the Heawood graph and its bipartite complement. (A bipartite complement of a bipartite graph X with bipartition V(X) = U ∪ W is the graph with vertex-set V(X) and edge-set {{u, w} : u ∈ U, w ∈ W, u  ∼X w}.) Another classical family of cyclic difference sets is essentially due to Paley [7] and can be described as follows. For a prime q congruent 3 modulo 4 let Fq denote the finite field of cardinality q and let D = {x2 | x ∈ Fq\ {0}} be the set of all non-zero squares in Fq . Then D is a difference set in the additive group of Fq . The corresponding symmetric design is exactly the Paley–Hadamard design defined in Sect. 1. The smallest non-trivial distance-regular dihedrants arising from this family are the incidence and the nonincidence graphs of the Paley–Hadamard design PalHad(7), which happen to be isomorphic to the Heawood graph and its bipartite complement, respectively, associated also with PG1 (2, 2). We remark that PalHad(11) is an exceptional symmetric design in many ways. It is, among other, responsible for the existence of the Mathieu group M11 . The corresponding distance-regular dihedrants, Dih (11; ∅, {1, 3, 4, 5, 9}) and its bipartite complement, also appear as exceptional distance-transitive dihedrants in Theorem 1.1. For other infinite families of cyclic difference sets we refer the reader to [3]. d+1

d

d−1

3 Distance-regular Cayley graphs, difference sets, and symmetric designs In this section, we discuss the relationship between general distance-regular Cayley graphs and difference sets. In Sect. 3.2 we then restrict our attention to distance-regular dihedrants, and discuss the relationship between these graphs and symmetric designs. Finally, in Sect. 3.3, we prove Theorem 1.1. 3.1 Distance-regular Cayley graphs and difference sets Lemma 3.1 Let k and µ be positive integers. A Cayley graph Cay(G; S) is a bipartite distance-regular graph with diameter 3 and intersection array {k, k − 1, k − µ; 1, µ, k} if and only if there exist disjoint subsets N2 , N3 ⊆ G\({1} ∪ S) such that {{1}, S, N2 , N3 } is a partition of G and the equalities

Des Codes Crypt (2006) 41: 185–193

189

S2 = k1G + µN2 ,

N2 S = (k − 1)S + kN3

(2)

hold in the group algebra ZG. In this case, N2 and N3 are exactly the sets of vertices at distance 2 and 3 from 1G , respectively. Proof Observe first that the equality NS=



αg g

(3)

g∈G

holds in ZG for a subset N ⊆ G if and only if every vertex g ∈ G of Cay(G; S) has exactly αg neighbours in the set N. If Cay(G; S) is a bipartite distance-regular graph with diameter 3 and intersection array {k, k − 1, k − µ; 1, µ, k}, then (3) immediately implies (2). Conversely, suppose that (2) holds for disjoint subsets N2 , N3 ⊆ G \ ({1} ∪ S). Note that k = |S| is the valency of Cay(G; S). Since Cay(G; S) is a vertex-transitive graph it suffices to prove the following: (a) (b) (c)

elements of S have no neighbours in S; N2 is the set of vertices at distance 2 from 1G in Cay(G; S) and every element in N2 has µ neighbours in S and no neighbours in N2 ; N3 is the set of vertices at distance 3 from 1G in Cay(G; S) and all the neighbours of every element of N3 belong to N2 .

Let g be an arbitrary vertex of Cay(G; S). If g is at distance 1 from 1G (that is, g ∈ S), then, by (2) and (3), it has no neighbours in S. This proves (a). Further, if g ∈ N2 , then by (2) and (3), g has µ neighbours in S and no neighbours in N2 . In particular, every element of N2 is at distance 2 from 1G . On the other hand, every element x ∈ G at distance 2 from 1G has to appear in the expansion of S2 in (2) with a positive coefficient, and thus belongs to N2 . This implies that N2 is the set of all vertices at distance 2 from 1G , and proves (b). Finally, if g ∈ N3 , then all of its k neighbours belong to N2 . In particular, every vertex in N3 is at distance at most 3 from 1G . On the other hand, every element x ∈ G at distance 3 from 1G has to have a neighbour in N2 and thus appears in the expansion of N2 S in (2) with a positive coefficient. Therefore, every vertex which is at distance 3 from 1G belongs to N3 . This proves (c) and completes the proof of the lemma.
Lemma 3.2 Let k and µ be positive integers, and let G be a group of order 2n and S a subset of G. Then the following statements are equivalent. (1) S ⊆ G \ {1}, S = S(−1) and Cay(G; S) is a bipartite non-trivial distance-regular graph with diameter 3 and intersection array {k, k − 1, k − µ; 1, µ, k}; (2) there is a subgroup H of index 2 in G such that for every a ∈ G\H, the set D = a−1 S is a non-trivial (n, k, µ)-difference set in H satisfying D(−1) = aDa; (3) there are a subgroup H of index 2 in G and an element a ∈ G\H such that the set D = a−1 S is a non-trivial (n, k, µ)-difference set in H satisfying D(−1) = aDa. Moreover, if (1)–(3) hold, then H \ {1} is exactly the set of vertices of Cay(G; S) which are at distance 2 from the vertex 1. Proof Suppose that (1) holds. For i ∈ {0, 1, 2, 3} let Ni denote the set of vertices at distance i from 1G in Cay(G; S). Clearly, the bipartition set H = N0 ∪ N2 forms a subgroup of index 2 in G. Let a be an arbitrary element of G\H and let D = a−1 S.

190

Des Codes Crypt (2006) 41: 185–193

Then D(−1) = S(−1) a = Sa = aDa. Moreover, by Lemma 3.1, DD(−1) = a−1 SS(−1) a = a−1 (k1G + µN2 )a = k1G + µN2 = (k − µ)1G + µH. Whence, D is a (n, k, µ)-difference set in H, showing that (2) holds. Clearly, (2) implies (3), therefore it remains to prove that (3) implies (1). Assume that (3) holds. Since a ∈ G \ H and D ⊆ H, we obtain S ∩ H = ∅. In particular, S ⊆ G\{1}. Moreover, it follows from D(−1) = aDa that S(−1) = D(−1) a−1 = aD = S. Let N2 = H \ {1} and let N3 = G \ (H ∪ S). Clearly {{1}, S, N2 , N3 } is a partition of G. Further, S2 = SS(−1) = aDD(−1) a−1 = a((k − µ)1G + µH)a−1 = k1G + µN2 , and N2 S = HS − S = aHD − S = kaH − S = k(G\H) − S = kN3 + kS − S = (k − 1)S + kN3 . Whence, by Lemma 3.1, (1) holds.
3.2 Distance-regular dihedrants and symmetric designs According to Theorem 2.1, all non-trivial distance-regular dihedrants arise in the context of difference sets. On the other hand, difference sets are closely related to symmetric designs. Recall that a symmetric (ν, k, µ)-design is an ordered pair (P , B) where P is a set of size ν and B is a collection of ν k-subsets of P such that two distinct points in P are simultaneously contained in exactly µ elements of B. Note that if (P , B) is a symmetric (ν, k, µ)-design, then (P , BC ), where BC = {P \ B | B ∈ B}, is a symmetric (ν, ν − k, ν − 2k + µ)-design, which is called the complement of (P , B). Clearly, the incidence graph of (P , BC ) is the non-incidence graph of (P , B). An automorphism of a symmetric design (P , B) is a permutation of the set P which maps every block in B to a block in B. A subgroup of the automorphism group of (P , B) which acts regularly on P is called a point-regular group of (P , B), or also a Singer group of (P , B). If G is a point-regular group of (P , B), then the induced action of G on B is also regular (see, e.g., [8, Proposition 1.2.3]). For a (ν, k, µ)-difference set D in a group G, let PD = G and BD = {gD | g ∈ G}. Then (PD , BD ) is a symmetric (ν, k, µ)-design with G acting by left multiplication pointregularly. Conversely, every symmetric (ν, k, µ)-design with a point-regular group isomorphic to G is isomorphic to the one obtained from a (ν, k, µ)-difference set in G as described above (see, e.g., [8, Theorem 1.2.5]). Note that if D is a difference set in G and DC = G\D is its complementary difference set in G, then (PD , BDC ) = (PD , BD C ). For a group H and a subgroup A ≤ Aut(H), we let A
H denote the semidirect product of H by A, that is, the set A × H with the product defined by (ϕ, g)(ψ, h) = (ϕψ, ψ −1 (g)h), for every ϕ, ψ ∈ A, g, h ∈ H. For a subset D ⊆ H and an element ϕ ∈ A, let (ϕ, D) = {(ϕ, h) | h ∈ D} ⊆ A
H. The following result will be used to prove that the graphs described in parts (2) and (3) of Theorem 2.1 are in fact the incidence graphs of the corresponding symmetric designs. But since it bears some interest of its own, we state it as a separate proposition. Proposition 3.3 Let k and µ be positive integers. If H is a group with an automorphism ϕ of order 2, then the following statements are equivalent. (1) Cay( ϕ
H; (ϕ, D)) is a bipartite non-trivial distance-regular graph with diameter 3 and intersection array {k, k − 1, k − µ; 1, µ, k}; (2) D is a non-trivial (|H|, k, µ)-difference set in H such that D(−1) = ϕ(D). Moreover, if (1) and (2) hold, then Cay( ϕ
H; (ϕ, D)) is isomorphic to the incidence graph of the symmetric design (PD , BD ). Proof To prove the equivalence of (1) and (2), define G = ϕ
H and observe that the implication (1) ⇒ (2) follows immediately from the implication (1) ⇒ (2)

Des Codes Crypt (2006) 41: 185–193

191

in Lemma 3.2, while the implication (2) ⇒ (1) follows from the implication (3) ⇒ (1) in Lemma 3.2. Now, suppose that (1) and (2) hold. Recall that PD = H and BD = {hD | h ∈ H}, and let f: ϕ
H → PD ∪ BD be the function defined by f (idH , h) = h ∈ PD and f (ϕ, h) = ϕ(h)D ∈ BD , for every h ∈ H. Note that f is bijective. Next, observe that two vertices x, y ∈ PD ∪ BD are adjacent in the incidence graph X of (PD , BD ) if and only if there exist h ∈ H and g ∈ D(−1) such that {x, y} = {h, hgD}. Furthermore, for arbitrary vertices u, v of Cay( ϕ
H; (ϕ, D)) and r, h ∈ H, the following equivalences hold: {u, v} = {(idH , h), (idH , h)(ϕ, r)} ⇔ {u, v} = {(idH , h), (ϕ, ϕ(hϕ(r)))} ⇔ {f (u), f (v)} = {h, hϕ(r)D}. Now, since u and v are adjacent in Cay( ϕ
H; (ϕ, D)) if and only if {u, v} = {(idH , h), (idH , h)(ϕ, r)} for some h ∈ H and r ∈ D, the above equivalences show that u and v are adjacent in Cay( ϕ
H; (ϕ, D)) if and only if {f (u), f (v)} = {h, hϕ(r)D} for some h ∈ H and r ∈ D. However, D(−1) = ϕ(D), hence ϕ(r) ∈ D(−1) whenever r ∈ D. Therefore, vertices u and v of Cay( ϕ
H; (ϕ, D)) are adjacent if and only if f (u), f (v) are adjacent in X. Since f is a bijection, this implies that Cay( ϕ
H; (ϕ, D)) and X are isomorphic.
Corollary 3.4 A connected graph X is a non-trivial distance-regular dihedrant on 2n vertices with intersection array R if and only if the diameter of X is 3, X is isomorphic to the incidence graph of the symmetric design (PD , BD ) where D is a non-trivial (n, k, µ)difference set in a group G, R = {k, k − 1, k − µ; 1, µ, k}, and one of the following holds: (1) G = Zn ; (2) n = 2m for an integer m, G = r, t | rm = t2 = (rt)2 = 1 ∼ = Dm , and D(−1) = ϕ(D), i −i where ϕ is the automorphism of G defined by ϕ(r ) = r , ϕ(ri t) = r−i+1 t. Proof Let ψ be the automorphism of the additive group of Zn defined by ψ(i) = −i. Further, if n = 2m for an integer m, let Dm = r, t | rm = t2 = (rt)2 = 1, and let ϕ be the automorphism of Dm as defined in part (2) above. Observe that the mappings f: Dn → ψ
Zn ,

f (ρ i ) = (id, i),

f (ρ i τ ) = (ψ, −i)

(4)

and g: Dn → ϕ
Dm ,

g(ρ 2i τ  ) = (id, ri t ),

g(ρ 2i+1 τ  ) = (ϕ, r−i t1− )

(5)

for i ∈ {0, . . . , m − 1} and  ∈ {0, 1}, are group isomorphisms. Suppose first that X is isomorphic to the incidence graph of the symmetric design (PD , BD ) where D is a non-trivial (n, k, µ)-difference set in the group Zn . By Proposition 3.3, X is isomorphic to Cay( ψ
Zn ; (ψ, D)) and is a non-trivial distanceregular graph with diameter 3 and the intersection array {k, k − 1, k − µ; 1, µ, k}. Since

ψ
Zn ∼ = Dn , X is also a dihedrant. Suppose now that n = 2m for an integer m, and that X is isomorphic to the incidence graph of the symmetric design (PD , BD ) where D is a non-trivial (n, k, µ)difference set in the group Dm such that D(−1) = ϕ(D). Then by Proposition 3.3, X is isomorphic to Cay( ϕ
Dm ; (ϕ, D)), and is a non-trivial distance-regular graph with

192

Des Codes Crypt (2006) 41: 185–193

diameter 3 and the intersection array {k, k − 1, k − µ; 1, µ, k}. Since ϕ
Dm ∼ = Dn , X is a dihedrant. Conversely, suppose that X is a non-trivial distance-regular dihedrant on 2n vertices. Let R be its intersection array. Then, by Theorem 2.1, X is bipartite and has diameter 3. Hence, R = (k, k − 1, k − µ; 1, µ, k) for some positive integers k, µ. Moreover, X is isomorphic to Dih (n; R, T) for some R, T ⊆ Zn such that one of the following holds: (a) R = ∅ and T is a non-trivial difference set in the group Zn ; (b) n = 2m for an integer m, R, T ⊆ 1 + 2Zn , and ρ −1+R ∪ ρ −1+T τ is a non-trivial difference set in ρ 2 , τ . If (a) occurs, we can apply the group isomorphism f on the vertex set of X to show that X is isomorphic to the Cayley graph Cay( ψ
Zn ; (ψ, −T)). By Proposition 3.3, D = −T is a non-trivial (n, k, µ)-difference set in Zn and X is isomorphic to the incidence graph of the symmetric design (PD , BD ). Suppose now that (b) occurs. Let R = {i | i ∈ {0, 1, . . . , m − 1}, 2i ∈ −1 + R} and  T = {i | i ∈ {0, 1, . . . , m−1}, 2i ∈ −1+T}. Since R, T ⊆ 1+2Zn , we see that R = {2i+1 |   i ∈ R } and T = {2i + 1 | i ∈ T  }. This implies that g(ρ R ∪ ρ T τ ) = (ϕ, r−T ∪ r−R t), and thus X = Cay(Dn ; ρ R ∪ ρ T τ ) is isomorphic to Cay( ϕ
Dm ; (ϕ, D)) where   D = r−T ∪ r−R t. By Proposition 3.3, D is a non-trivial (n, k, µ)-difference set such −1 that D = ϕ(D), and X is isomorphic to the incidence graph of the symmetric design (PD , BD ).
3.3 Proof of Theorem 1.1 Recall that a connected graph X with diameter d is said to be distance-transitive if for every integer i, 1 ≤ i ≤ d, the automorphism group Aut(X) acts transitively on the set {(u, v) | ∂X (u, v) = i}. Note that a connected vertex-transitive graph is distance-transitive if and only if the stabilizer Aut(X)u of a vertex u in X acts transitively on each sphere Si (u), 1 ≤ i ≤ d. The following lemma enables us to give an explicit description of all distance-transitive dihedrants. A group G is said to act doubly transitively on a set V if for any two pairs of distinct vertices (u1 , v1 ), (u2 , v2 ) ∈ V 2 , u1  = v1 , u2  = v2 , there exists an element α ∈ G such that u2 = α(u1 ) and v2 = α(v1 ). Note that a transitive permutation group G acts doubly transitively on V if and only if the vertex stabilizer Gu of a vertex u ∈ V acts transitively on G\{u}. Lemma 3.5 Suppose that the incidence graph X of a symmetric design (P , B) is vertex-transitive. Then X is distance-transitive if and only if the automorphism group of (P , B) acts doubly transitively on P . Proof Observe first that Aut(X) = G, ϕ, where G is the automorphism group of (P , B) and ϕ is an automorphism of X interchanging the bipartition sets P and B. Choose a vertex u ∈ P and observe that X is distance-transitive if and only if Gu acts transitively on each of the following three sets: S1 = {B ∈ B | u ∈ B}, S2 = P \{u} and S3 = {B ∈ B | u  ∈ B}. In particular, if X is distance-transitive, then Gu acts transitively on P \{u}, and hence G acts doubly transitively on P . Conversely, assume that G acts doubly transitively on P . Then Gu has 2 orbits on P . By the well-known Orbit Theorem (see [1, Theorem III.4.1]), Gu has exactly two orbits on B, which must clearly be S1 and S3 . Hence, X is distance-transitive.


Des Codes Crypt (2006) 41: 185–193

193

Corollary 3.4 now implies that every non-trivial distance-transitive dihedrant arises as an incidence graph of a symmetric design admitting an automorphism group acting doubly transitively on points and containing a point-regular cyclic or dihedral group. Symmetric designs with a doubly transitive point-group were classified in [4]. Besides the obvious complete designs and their complements (whose incidence graphs are complete bipratite graphs and void graphs, respectively), they are precisely the following designs: (1) (2) (3) (4)

Classical symmetric designs PGd−1 (d, q), and their complements; PalHad(11) and its complement; A pair of complementary designs with 176 points; A pair of complementary designs with 22m points, for each m ≥ 2.

None of these symmetric designs admit a point-regular action of a dihedral group, and those with a point-regular cyclic group are precisely PGd−1 (d, q), d ≥ 2, q a prime power, PalHad(11) and the complements of the above. This proves Theorem 1.1. Acknowledgments Authors were supported in part by “Ministrstvo za visoko šolstvo, znanost in tehnologijo Republike Slovenije”.

References 1. Beth T, Jungnickel D, Lenz H (1999) Design theory, vol 1, Second Edition, Encyclopedia of Mathematics and its Applications 69. Cambridge University Press, Cambridge 2. Brouwer AE, Cohen AM, Neumaier A (1998) Distance-regular graphs. Springer-Verlag, New York 3. Jungnickel D, Pott A (1996) Abelian difference sets. In: Coulbourn CJ, Dinitz JH (eds) The CRC hanbook of combinatorial designs. CRC Press, New York 4. Kantor W (1985) Classification of 2-transitive symmetric designs. Graphs Combin. 1:165–166 5. Miklaviˇc Š, Potoˇcnik P (2003) Distance-regular circulants. Eur J Combin 24:777–784 6. Miklaviˇc Š, Potoˇcnik P (xxxx) Distance-regular cayley graphs on dihedral groups accepted in J Combin Theory Ser B 7. Paley REAC (1933) On orthogonal matrices. J Math Phys MIT 12:311–320 8. Schmidt B (2002) Characters and cyclotomic fields in finite geometry. Lecture Notes in Mathematics 1797. Springer-Verlag, New York 9. Singer J (1938) A theorem in finite projective geometry and some applications to number theory. Trans Am Math Soc 43:377–385