Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 13–20
Line graphs and geodesic transitivity∗
Alice Devillers , Wei Jin , Cai Heng Li , Cheryl E. Praeger
Centre for the Mathematics of Symmetry and Computation, School of Mathematics and
Statistics, The University of Western Australia, Crawley, WA 6009, Australia
Received 21 October 2011, accepted 28 March 2012, published online 1 June 2012
Abstract
For a graph Γ, a positive integer s and a subgroup G ≤ Aut(Γ), we prove that G
is transitive on the set of s-arcs of Γ if and only if Γ has girth at least 2(s − 1) and G
is transitive on the set of (s − 1)-geodesics of its line graph. As applications, we first
classify 2-geodesic transitive graphs of valency 4 and girth 3, and determine which of them
are geodesic transitive. Secondly we prove that the only non-complete locally cyclic 2-
geodesic transitive graphs are the octahedron and the icosahedron.
Keywords: Line graphs, s-geodesic transitive graphs, s-arc transitive graphs.
Math. Subj. Class.: 05E18, 20B25
1 Introduction
A geodesic from a vertex u to a vertex v in a graph is a path of shortest length from u to
v. In the infinite setting geodesics play an important role, for example, in the classification
of infinite distance transitive graphs [11], and in studying locally finite graphs, see for
example, [17]. They are also used to model, in a finite network, the notion of visibility in
Euclidean space [22]. Here we study transitivity properties on geodesics in finite graphs.
Throughout this paper, we assume that all graphs are finite simple and undirected.
Let Γ be a connected graph with vertex set V (Γ), edge set E(Γ) and automorphism
group Aut(Γ). For a positive integer s, an s-arc of Γ is an (s+ 1)-tuple (v0, v1, . . . , vs) of
vertices such that vi, vi+1 are adjacent and vj−1 6= vj+1 for 0 ≤ i ≤ s− 1, 1 ≤ j ≤ s− 1;
it is an s-geodesic if in addition v0, vs are at distance s. For G ≤ Aut(Γ), Γ is said to
be (G, s)-arc transitive or (G, s)-geodesic transitive, if Γ contains an s-arc or s-geodesic,
∗This paper forms part of Australian Research Council Federation Fellowship FF0776186 held by the fourth
author. The first author is supported by UWA as part of the Federation Fellowship project during most of the
work for this paper. The second author is supported by the Scholarships for International Research Fees (SIRF)
at UWA.
E-mail addresses: alice.devillers@uwa.edu.au (Alice Devillers), 20535692@student.uwa.edu.au (Wei Jin),
cai.heng.li@uwa.edu.au (Cai Heng Li), cheryl.praeger@uwa.edu.au (Cheryl E. Praeger)
Copyright c© 2013 DMFA Slovenije
14 Ars Math. Contemp. 6 (2013) 13–20
and G is transitive on the set of t-arcs or t-geodesics respectively for all t ≤ s. Moreover,
if G = Aut(Γ), then G is usually omitted in the previous notation. The study of (G, s)-arc
transitive graphs goes back to Tutte’s papers [18, 19] which showed that if Γ is a (G, s)-arc
transitive cubic graph then s ≤ 5. About twenty years later, relying on the classification of
finite simple groups, Weiss [21] proved that there are no (G, 8)-arc transitive graphs with
valency at least three. The family of s-arc transitive graphs has been studied extensively,
see [2, 9, 15, 16, 20]. Here we consider these properties for line graphs.
The line graph L(Γ) of a graph Γ is the graph whose vertices are the edges of Γ, with
two edges adjacent in L(Γ) if they have a vertex in common. Our first aim in the paper
is to investigate connections between the s-arc transitivity of a connected graph Γ and the
(s − 1)-geodesic transitivity of its line graph L(Γ) where s ≥ 2. A key ingredient in this
study is a collection of injective maps Ls, where Ls maps the s-arcs of Γ to certain s-tuples
of edges of Γ (vertices of L(Γ)) as defined in Definition 2.3. The major properties of Ls
are derived in Theorem 2.4 and the main consequence linking the symmetry of Γ and L(Γ)
is given in Theorem 1.1, which is proved in Subsection 2.2.
We denote by Γ(u) the set of vertices adjacent to the vertex u in Γ. If |Γ(u)| is indepen-
dent of u ∈ V (Γ), then Γ is said to be regular. The girth of Γ is the length of the shortest
cycle; the diameter diam(Γ) of Γ is the maximum distance between two vertices.
Theorem 1.1. Let Γ be a connected regular, non-complete graph of girth g and valency at
least 3. LetG ≤ Aut(Γ) and let s be a positive integer such that 2 ≤ s ≤ diam(L(Γ))+1.
Then G is transitive on the set of s-arcs of Γ if and only if s ≤ g/2 + 1 and G is transitive
on the set of (s− 1)-geodesics of L(Γ).
It follows from a deep theorem of Richard Weiss in [21] that if Γ is a connected s-arc
transitive graph of valency at least 3, then s ≤ 7. This observation yields the following
corollary, and its proof can be found in Subsection 2.2.
Corollary 1.2. Let Γ and g be as in Theorem 1.1 . Let s be a positive integer such that
2 ≤ s ≤ diam(L(Γ)) + 1. If L(Γ) is (s− 1)-geodesic transitive, then either 2 ≤ s ≤ 7 or
s > max{7, g/2 + 1}.
Note that in a graph, 1-arcs and 1-geodesics are the same, and are called arcs. For
graphs of girth at least 4, each 2-arc is a 2-geodesic so the sets of 2-arc transitive graphs
and 2-geodesic transitive graphs are the same. However, there are also 2-geodesic transitive
graphs of girth 3. For such a graph Γ, the subgraph [Γ(u)] induced on the set Γ(u) is vertex
transitive and contains edges. Moreover, if [Γ(u)] is complete, then so is Γ. A vertex
transitive, non-complete, non-empty graph must have at least 4 vertices and thus valency 4
is the first interesting case.
As an application of Theorem 1.1, we characterise connected non-complete 2-geodesic
transitive graphs of girth 3 and valency 4. In this case, [Γ(u)] ∼= C4 or 2K2 for each
u ∈ V (Γ). If Γ is s-geodesic transitive with s = diam(Γ), then Γ is called geodesic
transitive. A graph Γ is said to be distance transitive if its automorphism group is transitive
on the ordered pairs of vertices at any given distance.
Theorem 1.3. Let Γ be a connected non-complete graph of girth 3 and valency 4. Then Γ
is 2-geodesic transitive if and only if Γ is either L(K4) ∼= O or L(Σ) for a connected 3-arc
transitive cubic graph Σ.
A. Devillers et al.: Line graphs and geodesic transitivity 15
Moreover, Γ is geodesic transitive if and only if Γ = L(Σ) for a cubic distance tran-
sitive graph Σ, namely Σ = K4, K3,3, the Petersen graph, the Heawood graph or Tutte’s
8-cage.
Since there are infinitely many 3-arc transitive cubic graphs, there are therefore in-
finitely many 2-geodesic transitive graphs with girth 3 and valency 4. Theorem 1.3 is
proved in Section 3, and it provides a useful method for constructing 2-geodesic transitive
graphs of girth 3 and valency 4 which are not geodesic transitive, an example being the line
graph of a triple cover of Tutte’s 8-cage constructed in [14]. The line graphs mentioned in
the second part of Theorem 1.3 are precisely the distance transitive graphs of valency 4 and
girth 3 given, for example, in [4, Theorem 7.5.3 (i)].
A graph Γ is said to be locally cyclic if [Γ(u)] is a cycle for every vertex u. In particular,
the girth of a locally cyclic graph is 3. It was shown in [8, Theorem 1.1] that for 2-geodesic
transitive graphs Γ of girth 3, the subgraph [Γ(u)] is either a connected graph of diameter
2, or isomorphic to the disjoint union mKr of m copies of a complete graph Kr with
m ≥ 2, r ≥ 2. Thus one consequence of Theorem 1.3 is a classification of connected,
locally cyclic, 2-geodesic transitive graphs in Corollary 1.4: for [Γ(u)] ∼= Cn has diameter
2 only for valencies n = 4 or 5, and the valency 5, girth 3, 2-geodesic transitive graphs
were classified in [7]. Its proof can be found at the end of Section 3. We note that locally
cyclic graphs are important for studying embeddings of graphs in surfaces, see for example
[10, 12, 13].
Corollary 1.4. Let Γ be a connected, non-complete, locally cyclic graph. Then Γ is 2-
geodesic transitive if and only if Γ is the octahedron or the icosahedron.
2 Line graphs
We begin by citing a well-known result about line graphs.
Lemma 2.1. [1, p.1455] Let Γ be a connected graph. If Γ has at least 5 vertices, then
Aut(Γ) ∼= Aut(L(Γ)).
The subdivision graph S(Γ) of a graph Γ is the graph with vertex set V (Γ) ∪ E(Γ)
and edge set {{u, e}|u ∈ V (Γ), e ∈ E(Γ), u ∈ e}. The link between the diameters of
Γ and S(Γ) was determined in [6, Remark 3.1 (b)]: diam(S(Γ)) = 2 diam(Γ) + δ for
some δ ∈ {0, 1, 2}. Here, based on this result, we will show the connection between the
diameters of Γ and L(Γ) in the following lemma.
Lemma 2.2. Let Γ be a connected graph with |V (Γ)| ≥ 2. Then it holds diam(L(Γ)) =
diam(Γ) + x for some x ∈ {−1, 0, 1}. Moreover, all three values occur, for example, if
Γ = K3+x, then diam(L(Γ)) = diam(Γ) + x = 1 + x for each x.
Proof. Let d = diam(Γ), dl = diam(L(Γ)) and ds = diam(S(Γ)). Let (x0, x2, . . . , x2dl)
be a dl-geodesic of L(Γ). Then by definition of L(Γ), each edge intersection x2i ∩ x2i+2
is a vertex v2i+1 of Γ and (x0, v1, x2, . . . , v2dl−1, x2dl) is a 2dl-path in S(Γ). Suppose that
(x0, v1, x2, . . . , v2dl−1, x2dl) is not a 2dl-geodesic of S(Γ). Then there is an r-geodesic
from x0 to x2dl , say (y0, y1, y2, . . . , yr) with y0 = x0 and yr = x2dl , such that r < 2dl.
Since both x0, x2dl are in V (L(Γ)), it follows that r is even, and hence dL(Γ)(x0, x2dl) =
r
2 < dl which contradicts the fact that (x0, x2, . . . , x2dl) is a dl-geodesic of L(Γ). Thus
16 Ars Math. Contemp. 6 (2013) 13–20
(x0, v1, x2, . . . , v2dl−1, x2dl) is a 2dl-geodesic in S(Γ). It follows from [6, Remark 3.1
(b)] that dl ≤ ds/2 ≤ d+ 1.
Now take a ds-geodesic (x0, x1, . . . , xds) in S(Γ). If x0 ∈ E(Γ), then (x0, x2, x4, . . . ,
x2bds/2c) is a bds/2c-geodesic in L(Γ), so dl ≥ bds/2c ≥ d. Similarly we see that dl ≥ d
if xds ∈ E(Γ). Finally if both x0, xds ∈ V (Γ), then ds is even and dΓ(x0, xds) = ds/2.
Moreover (x1, x3, . . . , xds−1) is a (
ds−2
2 )-geodesic in L(Γ). By [6, Remark 3.1 (b)], ds =
2d, so dl ≥ ds−22 = d− 1.
2.1 The map Ls
Let Γ be a finite connected graph. For each integer s ≥ 2, we define a map from the set of
s-arcs of Γ to the set of s-tuples of V (L(Γ)).
Definition 2.3. Let a = (v0, v1, . . . , vs) be an s-arc of Γ where s ≥ 2, and for 0 ≤ i < s,
let ei := {vi, vi+1} ∈ E(Γ). Define Ls(a) := (e0, e1, . . . , es−1).
The following theorem gives some important properties of Ls.
Theorem 2.4. Let s ≥ 2, let Γ be a connected graph containing at least one s-arc, and let
Ls be as in Definition 2.3. Then the following statements hold.
(1) Ls is an injective map from the set of s-arcs of Γ to the set of (s− 1)-arcs of L(Γ).
Further, Ls is a bijection if and only if either s = 2, or s ≥ 3 and Γ ∼= Cm or Pn for some
m ≥ 3, n ≥ s.
(2) Ls maps s-geodesics of Γ to (s− 1)-geodesics of L(Γ).
(3) If s ≤ diam(L(Γ)) + 1, then the image Im(Ls) contains the set Gs−1 of all (s−1)-
geodesics of L(Γ). Moreover, Im(Ls) = Gs−1 if and only if girth(Γ) ≥ 2s− 2.
(4) Ls is Aut(Γ)-equivariant, that is, Ls(a)g = Ls(ag) for all g ∈ Aut(Γ) and all
s-arcs a of Γ.
Proof. (1) Let a = (v0, v1, . . . , vs) be an s-arc of Γ and let Ls(a) := (e0, e1, . . . , es−1)
with the ei as in Definition 2.3. Then each of the ei lies inE(Γ) = V (L(Γ)) and ek 6= ek+1
for 0 ≤ k ≤ s−2. Further, since vj 6= vj+1, vj+2 for 1 ≤ j ≤ s−2, we have ej−1 6= ej+1.
Thus Ls(a) is an (s− 1)-arc of L(Γ).
Let b = (u0, u1, . . . , us) and c = (w0, w1, . . . , ws) be two s-arcs of Γ. Then Ls(b) =
(f0, f1, . . . , fs−1) and Ls(c) = (g0, g1, . . . , gs−1) are two (s − 1)-arcs of L(Γ), where
fi = {ui, ui+1} and gi = {wi, wi+1} for 0 ≤ i < s. Suppose that Ls(b) = Ls(c). Then
fi = gi for each i ≥ 0, and hence fi ∩ fi+1 = gi ∩ gi+1, that is, ui+1 = wi+1 for each
0 ≤ i ≤ s− 2. So also u0 = w0 and us = ws, and hence b = c. Thus Ls is injective.
Now we prove the second part. Each arc of L(Γ) is of the form h = (e, f) where
e = {u0, u1} and f = {u1, u2} are distinct edges of Γ. Thus u0 6= u2, so k = (u0, u1, u2)
is a 2-arc of Γ and L2(k) = h. It follows that L2 is onto and hence is a bijection. If s ≥ 3
and Γ ∼= Cm or Pn for some m ≥ 3, n ≥ s, then L(Γ) ∼= Cm or Pn−1 respectively, and
hence for every (s−1)-arc x of L(Γ), we can find an s-arc y of Γ such that Ls(y) = x, that
is, Ls is onto. Thus Ls is a bijection. Conversely, suppose that Ls is onto, and that s ≥ 3.
Assume that some vertex u of Γ has valency greater than 2 and let e1 = {u, v1}, e2 =
{u, v2}, e3 = {u, v3} be distinct edges. Then x = (e1, e2, e3) is a 2-arc in L(Γ) and there
is no 3-arc y of Γ such that Ls(y) = x. In general, for s = 3a + b ≥ 4 with a ≥ 1 and
b ∈ {0, 1, 2}, we concatenate a copies of x to form an (s − 1)-arc of L(Γ): namely (xa)
if b = 0; (xa, e1) if b = 1; (xa, e1, e2) if b = 2. This (s− 1)-arc does not lie in the image
A. Devillers et al.: Line graphs and geodesic transitivity 17
of Ls. Thus each vertex of Γ has valency at most 2. If all vertices have valency 2 then
Γ ∼= Cm for some m ≥ 3, since Γ is connected. So suppose that some vertex u of Γ has
valency 1. Since Γ is connected and each other vertex has valency at most 2, it follows that
Γ ∼= Pn for some n ≥ s.
(2) Let a = (v0, . . . , vs) be an s-geodesic of Γ and let Ls(a) = (e0, . . . , es−1) as
above. If s = 2, then Ls(a) is a 1-arc, and hence a 1-geodesic of L(Γ). Suppose that
s ≥ 3 and Ls(a) is not an (s − 1)-geodesic. Then dL(Γ)(e0, es−1) = r < s − 1 and
there exists an r-geodesic r = (f0, f1, . . . , fr−1, fr) with f0 = e0 and fr = es−1. Since
s ≥ 3 and a is an s-geodesic, it follows that {v0, v1} ∩ {vs−1, vs} = ∅, that is, e0 and
es−1 are not adjacent in L(Γ). Thus r ≥ 2. Since r is an r-geodesic, it follows that the
consecutive edges fi−1, fi, fi+1 do not share a common vertex for any 1 ≤ i ≤ r − 1,
otherwise (f0, . . . , fi−1, fi+1, . . . , fr) would be a shorter path than r, which is impossible.
Hence we have fh = {uh, uh+1} for 0 ≤ h ≤ r. Then (u1, u2, . . . , ur) is an (r − 1)-path
in Γ, {u1} = e0 ∩ f1 ⊆ {v0, v1} and {ur} = fr−1 ∩ es−1 ⊆ {vs−1, vs}. It follows that
dΓ(v0, vs) ≤ dΓ(u1, ur) + 2 ≤ r + 1 < s, contradicting the fact that a is an s-geodesic.
Therefore, Ls(a) is an (s− 1)-geodesic of L(Γ).
(3) Let 2 ≤ s ≤ diam(L(Γ)) + 1 and Gs−1 be the set of all (s− 1)-geodesics of L(Γ).
If s = 2, then by part (1), each 1-geodesic of L(Γ) lies in the image Im(L2), and hence
G1 ⊆ Im(L2). Now suppose inductively that 2 ≤ s ≤ diam(L(Γ)) and Gs−1 ⊆ Im(Ls).
Let e = (e0, e1, e2, . . . , es) be an s-geodesic of L(Γ). Then e′ = (e0, e1, e2, . . . , es−1)
is an (s − 1)-geodesic of L(Γ). Thus there exists an s-arc a of Γ such that Ls(a) = e′,
say a = (v0, v1, . . . , vs). Since es is adjacent to es−1 = {vs−1, vs} but not to es−2 =
{vs−2, vs−1} in L(Γ), it follows that es = {vs, x} where x /∈ {vs−2, vs−1}. Hence b =
(v0, v1, . . . , vs, x) is an (s + 1)-arc of Γ. Further, Ls+1(b) = e. Thus Im(Ls+1) contains
all s-geodesics of L(Γ), that is, Gs ⊆ Im(Ls+1). Hence the first part of (3) is proved by
induction.
Now we prove the second part. Suppose first that for every s-arc a of Γ, Ls(a) is an
(s − 1)-geodesic of L(Γ). Let g := girth(Γ). If s = 2, as g ≥ 3, then g ≥ 2s − 2. Now
let s ≥ 3. Assume that g ≤ 2s − 3. Then Γ has a g-cycle b = (u0, u1, u2, . . . , ug−1, ug)
with ug = u0. It follows that Lg(b) forms a g-cycle of L(Γ). Thus the sequence b′ =
(u0, u1, . . . , us) (where we take subscripts modulo g if necessary) is an s-arc of Γ and
Ls(b′) = (e0, e1, . . . , es−1) involves only the vertices of Ls(b). This implies that
dL(Γ)(e0, es−1) ≤ g2 ≤
2s−3
2 < s− 1, that is, Ls(b
′) is not an (s− 1)-geodesic, which is
a contradiction. Thus, g ≥ 2s− 2.
Conversely, suppose that g ≥ 2s − 2. Let a := (v0, v1, v2, . . . , vs) be an s-arc of
Γ. Then Ls(a) = (e0, e1, e2, . . . , es−1) is an (s − 1)-arc of L(Γ) by part (1). Let a′ :=
(v0, v1, v2, . . . , vs−1). Since g ≥ 2s − 2, it follows that a′ is an (s − 1)-geodesic, and
hence by (2), Ls−1(a′) = (e0, e1, e2, . . . , es−2) is an (s − 2)-geodesic of L(Γ). Thus
z = dL(Γ)(e0, es−1) satisfies s−3 ≤ z ≤ s−1. There is a z-geodesic from e0 to es−1, say
f = (e0, f1, f2, . . . , fz−1, es−1). Further, by the first part of (3), there is a (z + 1)-arc b =
(u0, u1, . . . , uz, uz+1) of Γ such that Lz+1(b) = f and we have e0 = {u0, u1} = {v0, v1}
and es−1 = {uz, uz+1} = {vs−1, vs}. There are 4 cases, in columns 2 and 3 of Table 1: in
each case there is a given nondegenerate closed walk x of length l(x) as in Table 1. Thus
l(x) ≥ g ≥ 2s− 2 and in each case l(x) ≤ s+ z − 1. It follows that z ≥ s− 1, and hence
z = s− 1. Thus Ls(a) = (e0, e1, e2, . . . , es−1) is an (s− 1)-geodesic of L(Γ).
(4) This property follows from the definition of Ls.
18 Ars Math. Contemp. 6 (2013) 13–20
Table 1: Four cases of x
Case (u0, u1) (uz, uz+1) x l(x)
1 (v0, v1) (vs−1, vs) (vs−1, vs−2, . . . , v2, v1, u2, . . . , s+ z − 3
uz−1, vs−1)
2 (v0, v1) (vs, vs−1) (vs, vs−1, . . . , v2, v1, u2, . . . , s+ z − 2
uz−1, vs)
3 (v1, v0) (vs−1, vs) (vs−1, vs−2, . . . , v2, v1, u1, u2, . . . , s+ z − 2
uz−1, vs−1)
4 (v1, v0) (vs, vs−1) (vs, vs−1, . . . , v2, v1, u1, u2, . . . , s+ z − 1
uz−1, vs)
Remark 2.5. (i) The map Ls is usually not surjective on the set of (s − 1)-arcs of L(Γ).
In the proof of Theorem 2.4 (1), we constructed an (s − 1)-arc of L(Γ) not in Im(Ls) for
any Γ with at least one vertex of valency at least 3.
(ii) Theorem 2.4 (1) and (3) imply that, for each (s − 1)-geodesic e of L(Γ), there is
a unique s-arc a of Γ such that Ls(a) = e. The s-arc a is not always an s-geodesic. For
example, if Γ has girth 3 and (v0, v1, v2, v0) is a 3-cycle, then a = (v0, v1, v2) is not a
2-geodesic but L2(a) is the 1-geodesic (e0, e1) where e0 = {v0, v1} and e1 = {v1, v2}.
2.2 Proofs of Theorem 1.1 and Corollary 1.2
Proof of Theorem 1.1. Let Γ be a connected, regular, non-complete graph of girth g
and valency at least 3. Then in particular |V (Γ)| ≥ 5, and by Lemma 2.1, Aut(Γ) ∼=
Aut(L(Γ)). Let G ≤ Aut(Γ) and let 2 ≤ s ≤ diam(L(Γ)) + 1.
Suppose first thatG is transitive on the set of s-arcs of Γ. Then by [3, Proposition 17.2],
s ≤ g/2 + 1. Since s − 1 ≤ diam(L(Γ)), it follows that L(Γ) has (s − 1)-geodesics and
by Theorem 2.4 (3), Im(Ls) is the set of (s − 1)-geodesics of L(Γ). On the other hand,
by Theorem 2.4 (4), G acts transitively on Im(Ls), and hence G is transitive on the set of
(s− 1)-geodesics of L(Γ).
Conversely, suppose that s ≤ g/2 + 1 and G is transitive on the (s − 1)-geodesics of
L(Γ). Then by the last assertion of Theorem 2.4 (3), Im(Ls) is the set of (s−1)-geodesics,
and since Ls is injective, it follows from Theorem 2.4 (1) and (4) that G is transitive on the
set of s-arcs of Γ. 
Proof of Corollary 1.2. Let Γ, g, s be as in Theorem 1.1. Assume that Aut(Γ) is transitive
on the (s − 1)-geodesics of L(Γ). If s > 7, then by [21], Aut(Γ) is not transitive on the
s-arcs of Γ and so by Theorem 1.1, s > g2 + 1. 
3 2-geodesic transitive graphs that are locally cyclic or locally 2K2
In this section, we prove Theorem 1.3. The proof uses the notion of a clique graph. A
maximum clique of a graph Γ is a clique (complete subgraph) which is not contained in a
larger clique. The clique graph C(Γ) of Γ is the graph with vertices the maximum cliques
of Γ, and two maximum cliques are adjacent if and only if they have at least one common
vertex in Γ.
A. Devillers et al.: Line graphs and geodesic transitivity 19
Proof of Theorem 1.3. Let Γ be a connected non-complete graph of girth 3 and valency 4,
and let A = Aut(Γ) and v ∈ V (Γ). Suppose first that Γ is 2-geodesic transitive. Then Γ
is arc transitive, and so Av is transitive on Γ(v). Since Γ is non-complete of girth 3, [Γ(v)]
is neither complete nor edgeless, and so, as discussed before the statement of Theorem
1.3, [Γ(v)] = C4 or 2K2. If [Γ(v)] ∼= C4, then it is easy to see that Γ ∼= O (or see [4,
p.5] or [5]). So we may assume that [Γ(v)] ∼= 2K2. It follows from [8, Theorem 1.4]
that Γ is isomorphic to the clique graph C(Σ) of a connected graph Σ such that, for each
u ∈ V (Σ), the induced subgraph [Σ(u)] ∼= 3K1, that is to say, Σ is a cubic graph of girth
at least 4 and C(Σ) is in this case the line graph L(Σ). Moreover, [8, Theorem 1.4] gives
that Σ ∼= C(Γ). A cubic graph with girth at least 4 has |V (Σ)| ≥ 5, so by Lemma 2.1,
A ∼= Aut(Σ). Now we apply Theorem 1.1 to the graph Σ of girth g ≥ 4. Since Γ = L(Σ)
is 2-geodesic transitive and 3 ≤ g/2 + 1, it follows from Theorem 1.1 that Σ is 3-arc
transitive. Therefore, Γ is the line graph of a 3-arc transitive cubic graph.
Conversely, if Γ ∼= O, then it is 2-geodesic transitive, and hence is geodesic transitive
as diam(O) = 2. If Γ = L(Σ) where Σ is a 3-arc transitive cubic graph, then by Theorem
1.1 applied to Σ with s = 3, L(Σ) is 2-geodesic transitive. This proves the first assertion
of Theorem 1.3.
To prove the second assertion, suppose first that Γ is geodesic transitive. Then Γ is
distance transitive, and so by Theorems 7.5.2 and 7.5.3 (i) of [4], Γ is one of the following
graphs: O = L(K4), H(2, 3) = L(K3,3), or the line graph of the Petersen graph, the
Heawood graph or Tutte’s 8-cage. We complete the proof by showing that all these graphs
are geodesic transitive. As noted above, O is geodesic transitive; by [7, Proposition 3.2],
H(2, 3) is geodesic transitive. It remains to consider the last three graphs.
Let Σ be the Petersen graph and Γ = L(Σ). Then Σ is 3-arc transitive, and it follows
from Theorem 1.1 that Γ is 2-geodesic transitive. By [4, Theorem 7.5.3 (i)], diam(Γ) = 3
and |Γ(w)∩Γ3(u)| = 1 for each 2-geodesic (u, v, w) of Γ. Thus Γ is 3-geodesic transitive,
and hence is geodesic transitive.
Let Σ1 be the Heawood graph and Σ2 be Tutte’s 8-cage. Then Σ1 is 4-arc transitive and
Σ2 is 5-arc transitive, and hence by Theorem 1.1, L(Σ1) is 3-geodesic transitive and L(Σ2)
is 4-geodesic transitive. By [4, Theorem 7.5.3 (i)], diam(L(Σ1)) = 3 and diam(L(Σ2)) =
4, and hence both L(Σ1) and L(Σ2) are geodesic transitive. 
Finally, we prove Corollary 1.4.
Proof of Corollary 1.4. Let Γ be a connected non-complete locally cyclic graph. If Γ is
2-geodesic transitive, then it is regular of valency n say. As discussed in the introduction,
n = 4 or 5. If n = 4, then we proved in Theorem 1.3, that Γ is isomorphic to the octahedron
and that the octahedron is indeed 2-geodesic transitive. If n = 5, then by [7, Theorem 1.2],
Γ is isomorphic to the icosahedron, and this graph is 2-geodesic transitive. 
Acknowledgements
This article forms part of the second author’s Ph.D thesis at UWA under the supervision
of other authors. The authors are grateful to Sandi Malnič for suggesting that we consider
s-geodesic transitivity for locally cyclic graphs. They also thank the anonymous referees
for valuable suggestions on the exposition.
20 Ars Math. Contemp. 6 (2013) 13–20
References
[1] L. Babai, Automorphism Groups, Isomorphism, Reconstruction, Handbook of Combinatorics,
the MIT Press, Cambridge, Massachusetts, Amsterdam-Lausanne-New York, Vol 2, (1995),
1447–1540.
[2] R. W. Baddeley, Two-arc transitive graphs and twisted wreath products. J. Algebraic Combin.
2 (1993), 215–237.
[3] N. L. Biggs, Algebraic Graph Theory, Second ed., Cambridge University Press, Cambridge,
(1993).
[4] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer Verlag,
Berlin, Heidelberg, New York, (1989).
[5] A. M. Cohen, Local recognition of graphs, buildings, and related geometries, in: W. M. Kantor,
R. A. Liebler, S. E. Payne, E. E. Shult (eds.), Finite Geometries, Buildings, and related Topics,
Oxford Sci. Publ., New York. 19 (1990), 85–94.
[6] A. Daneshkhah, A. Devillers and C. E. Praeger, Symmetry properties of subdivision graphs,
Discrete Math. 312 (2012), 86–93.
[7] A. Devillers, W. Jin, C. H. Li and C. E. Praeger, On distance, geodesic and arc transitivity of
graphs, preprint, 2011, available at http://arxiv.org/abs/1110.2235.
[8] A. Devillers, W. Jin, C. H. Li and C. E. Praeger, Local 2-geodesic transitivity and clique graphs,
in preparation.
[9] A. A. Ivanov and C. E. Praeger, On finite affine 2-arc transitive graphs, European J. Combin.
14 (1993), 421–444.
[10] M. Juvan, A. Malnič and B. Mohar, Systems of curves on surfaces, J. Combin. Theory Ser. B
68 (1996), 7–22.
[11] H. D. Macpherson, Infinite distance transitive graphs of finite valency, Combinatorica 2 (1982),
63–69.
[12] A. Malnič and B. Mohar, Generating locally cyclic triangulations of surfaces, J. Combin. The-
ory Ser. B 56 (1992), 147–164.
[13] A. Malnič and R. Nedela, K-Minimal triangulations of surfaces, Acta Math. Univ. Comenianae
LXIV 1 (1995), 57–76.
[14] M. J. Morton, Classification of 4 and 5-arc transitive cubic graphs of small girth, J. Austral.
Math. Soc. A 50 (1991), 138–149.
[15] C. E. Praeger, An O’Nan Scott theorem for finite quasiprimitive permutation groups and an
application to 2-arc transitive graphs, J. London Math. Soc. 47 (1993), 227–239.
[16] C. E. Praeger, On a reduction theorem for finite, bipartite, 2-arc transitive graphs, Australas. J.
Combin. 7 (1993) 21–36.
[17] C. Thomassen and W. Woess, Vertex-transitive graphs and accessibility, J. Combin. Theory Ser.
B 58 (1993), 248–268.
[18] W. T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (1947), 459–474.
[19] W. T. Tutte, On the symmetry of cubic graphs, Canad. J. Math. 11 (1959), 621–624.
[20] R. Weiss, s-transitive graphs, Algebraic methods in graph theory, Vol. I, II, (Szeged, 1978),
Colloq. Math. Soc. Janos Bolyai, 25, North-Holland, Amsterdam-New York, (1981), 827–847.
[21] R. Weiss, The non-existence of 8-transitive graphs, Combinatorica 1 (1981), 309–311.
[22] A. Y. Wu and A. Rosenfeld, Geodesic visibility in graphs, J. Information Sciences 108 (1998),
5–12.