Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 221–236
Orienting and separating
distance-transitive graphs
Ítalo J. Dejter
University of Puerto Rico, Rio Piedras, PR 00936-8377, Puerto Rico
Received 3 October 2011, accepted 7 March 2012, published online 6 September 2012
Abstract
It is shown that exactly 7 distance-transitive cubic graphs among the existing 12 possess
a particular ultrahomogeneous property with respect to oriented cycles realizing the girth
that allows the construction of a related Cayley digraph with similar ultrahomogeneous
properties in which those oriented cycles appear minimally “pulled apart”, or “separated”
and whose description is truly beautiful and insightful. This work is proposed as the ini-
tiation of a study of similar ultrahomogeneous properties for distance-transitive graphs in
general with the aim of generalizing to constructions of similar related “separator” Cayley
digraphs.
Keywords: Distance-transitive graph, ultrahomogeneous graph, Cayley graph.
Math. Subj. Class.: 05C62, 05B30, 05C20, 05C38
1 Introduction
A graph is said to be distance-transitive if its automorphism group acts transitively on
ordered pairs of vertices at distance i, for each i ≥ 0 [3, 10, 15]. In this paper we deal
mainly with finite cubic distance-transitive graphs. While these graphs are classified and
very well-understood since there are only twelve examples, for this very restricted class
of graphs we investigate a property called ultrahomogeneity that plays a very important
role in logic, see for example [7, 18]. For ultrahomogeneous graphs (resp. digraphs), we
refer the reader to [5, 9, 11, 17, 19] (resp. [6, 8, 16]). Distance-transitive graphs and
ultrahomogeneous graphs are very important and worthwhile to investigate. However, to
start with, the following question is answered in the affirmative for 7 of the 12 existing
cubic distance-transitive graphs G and negatively for the remaining 5:
Question 1.1. If k is the largest ` such that G is `-arc-transitive, is it possible to orient all
shortest cycles of G so that each two oppositely oriented (k − 1)-arcs of G are just in two
corresponding oriented shortest cycles?
E-mail address: ijdejter@uprrp.edu (Ítalo J. Dejter)
Copyright c© 2013 DMFA Slovenije
222 Ars Math. Contemp. 6 (2013) 221–236
The answer (below) to Question 1 leads to 7 connected digraphs S(G) in which all ori-
ented shortest cycles of G are minimally “pulled apart” or “separated”. Specifically, it is
shown that all cubic distance-transitive graphs are {Cg}Pk -ultrahomogeneous, where g =
girth, but only the 7 cited G are { ~Cg}~Pk -ultrahomogeneous digraphs and in each of these
7 digraphs G, the corresponding “separator” digraph S(G) is: (a) vertex-transitive digraph
of indegree = outdegree = 2, underlying cubic graph and automorphism group as that of G;
(b) { ~Cg, ~C2}-ultrahomogeneous digraph, where ~Cg = induced oriented g-cycle, with each
vertex taken as the intersection of exactly one such ~Cg and one ~C2; (c) a Cayley digraph.
The structure and surface-embedding topology [2, 12, 20] of these S(G) are studied as
well. We remark that the description of these S(G) is truly beautiful and insightful.
It remains to see how Question 1 can be generalized and treated for distance-transitive
graphs of degree larger than 3 and what separator Cayley graphs could appear via such a
generalization.
2 Preliminaries
We may consider a graph G as a digraph by taking each edge e of G as a pair of oppositely
oriented (or O-O) arcs ~e and (~e)−1 inducing an oriented 2-cycle ~C2. Then, fastening ~e
and (~e)−1 allows to obtain precisely the edge e in the graph G. Is it possible to orient all
shortest cycles in a distance-transitive graph G so that each two O-O (k − 1)-arcs of G are
in just two oriented shortest cycles, where k = largest ` such that G is `-arc transitive? It is
shown below that this is so just for 7 of the 12 cubic distance-transitive graphsG, leading to
7 corresponding minimum connected digraphs S(G) in which all oriented shortest cycles
of G are “pulled apart” by means of a graph-theoretical operation explained in Section 4
below.
Given a collection C of (di)graphs closed under isomorphisms, a (di)graph G is said to be
C-ultrahomogeneous (or C-UH) if every isomorphism between two induced members of C
in G extends to an automorphism of G. If C is the isomorphism class of a (di)graph H ,
we say that such a G is {H}-UH or H-UH. In [14], C-UH graphs are defined and studied
when C is the collection of either the complete graphs, or the disjoint unions of complete
graphs, or the complements of those unions.
Let M be an induced subgraph of a graph H and let G be both an M -UH and an H-UH
graph. We say that G is an {H}M -UH graph if, for each induced copy H0 of H in G and
for each induced copy M0 of M in H0, there exists exactly one induced copy H1 6= H0
of H in G with V (H0) ∩ V (H1) = V (M0) and E(H0) ∩ E(H1) = E(M0). The vertex
and edge conditions above can be condensed as H0 ∩H1 = M0. We say that such a G is
tightly fastened. This is generalized by saying that an {H}M -UH graph G is an `-fastened
{H}M -UH graph if given an induced copyH0 ofH inG and an induced copyM0 ofM in
H0, then there exist exactly ` induced copiesHi 6= H0 ofH inG such thatHi∩H0 ⊇M0,
for each i = 1, 2, . . . , `, with at least H1 ∩H0 = M0.
Let ~M be an induced subdigraph of a digraph ~H and let the graphG be both an ~M -UH and
an ~H-UH digraph. We say that G is an { ~H} ~M -UH digraph if for each induced copy ~H0 of
~H in ~G and for each induced copy ~M0 of ~M in ~H0 there exists exactly one induced copy
I. J. Dejter: Orienting and separating distance-transitive graphs 223
~H1 6= ~H0 of ~H in G with V ( ~H0) ∩ V ( ~H1) = V ( ~M0) and A( ~H0) ∩ Ā( ~H1) = A( ~M0),
where Ā( ~H1) is formed by those arcs (~e)−1 whose orientations are reversed with respect
to the orientations of the arcs ~e of A( ~H1). Again, we say that such a G is tightly fastened.
This case is used in the constructions of Section 4.
Given a finite graph H and a subgraph M of H with |V (H)| > 3, we say that a graph
G is (strongly fastened) SF {H}M -UH if there is a descending sequence of connected
subgraphs M = M1,M2 . . . ,Mt ≡ K2 such that: (a) Mi+1 is obtained from Mi by the
deletion of a vertex, for i = 1, . . . , t−1 and (b)G is a (2i−1)-fastened {H}Mi -UH graph,
for i = 1, . . . , t.
This paper deals with the above defined C-UH concepts applied to cubic distance-transitive
(CDT) graphs [3]. A list of them and their main parameters follows:
CDT graph G n d g k η a b h κ
Tetrahedral graph K4
Thomsen graph K3,3
4
6
1
2
3
4
2
3
4
9
24
72
0
1
1
1
1
2
3-cube graph Q3
Petersen graph
8
10
3
2
4
5
2
3
6
12
48
120
1
0
1
0
1
0
Heawood graph
Pappus graph
14
18
3
4
6
6
4
3
28
18
336
216
1
1
1
1
0
0
Dodecahedral graph
Desargues graph
20
20
5
5
5
6
2
3
12
20
120
240
0
1
1
1
1
3
Coxeter graph
Tutte 8-cage
28
30
4
4
7
8
3
5
24
90
336
1440
0
1
0
1
3
2
Foster graph
Biggs-Smith graph
90
102
8
7
10
9
5
4
216
136
4320
2448
1
0
1
1
0
0
where n = order; d = diameter; g = girth; k = AT or arc-transitivity (= largest ` such that
G is `-arc transitive); η = number of g-cycles; a = number of automorphisms; b (resp. h)
= 1 if G is bipartite (resp. hamiltonian) and = 0 otherwise; and κ is defined as follows:
let Pk and ~Pk be respectively a (k − 1)-path and a directed (k − 1)-path (of length k − 1);
let Cg and ~Cg be respectively a cycle and a directed cycle of length g; then (see Theorem 3
below): κ = 0, if G is not ( ~Cg; ~Pk)-UH; κ = 1, if G is planar; κ = 2, if G is { ~Cg} ~Pk -UH
with g = 2(k − 1); κ = 3, if G is { ~Cg} ~Pk -UH with g > 2(k − 1).
In Section 3 below, Theorem 2 proves that every CDT graph is an SF {Cg}Pk -UH graph,
while Theorem 3 establishes exactly which CDT graphs are not { ~Cg} ~Pk -UH digraphs; in
fact 5 of them. Section 4 shows that each of the remaining 7 CDT graphsG yields a digraph
S(G) whose vertices are the (k − 1)-arcs of G, an arc in S(G) between each two vertices
representing corresponding (k − 1)-arcs in a common oriented g-cycle of G and sharing
just one (k − 2)-arc; additional arcs of S(G) appearing in O-O pairs associated with the
reversals of (k − 1)-arcs of G. Moreover, Theorem 4 asserts that each S(G) is as claimed
and itemized at end of the Introduction above.
3 (Cg, Pk)-UH properties of CDT graphs
Theorem 3.1. Let G be a CDT graph of girth = g, AT = k and order = n. Then, G is an
SF {Cg}Pk -UH graph. In particular, G has exactly 2k−23ng−1 g-cycles.
224 Ars Math. Contemp. 6 (2013) 221–236
Proof. We have to see that each CDT graph G with girth = g and AT = k is a (2i+1 − 1)-
fastened {Cg}Pk−i -UH graph, for i = 0, 1, . . . , k − 2. In fact, each (k − i − 1)-path
P = Pk−i of any such G is shared by exactly 2i+1 g-cycles of G, for i = 0, 1, . . . , k − 2.
For example if k = 4, then any edge (resp. 2-path, resp. 3-path) of G is shared by 8 (resp.
4, resp. 2) g-cycles of G. This means that a g-cycle Cg of G shares a P2 (resp. P3, resp.
P4) with exactly other 7 (resp. 3, resp. 1) g-cycles. Thus G is an SF {Cg}Pi+2 -UH graph,
for i = 0, 1, . . . , k − 2. The rest of the proof depends on the particular cases analyzed in
the proof of Theorem 3 below and on some simple counting arguments for the pertaining
numbers of g-cycles.
Given a CDT graph G, there are just two g-cycles shared by each (k − 1)-path. If in ad-
dition G is a {~Cg}~Pk -UH graph, then there exists an assignment of an orientation for each
g-cycle of G, so that the two g-cycles shared by each (k − 1)-path receive opposite orien-
tations. We say that such an assignment is a {~Cg}~Pk -O-O assignment (or {
~Cg}~Pk -OOA).
The collection of η oriented g-cycles corresponding to the η g-cycles of G, for a partic-
ular {~Cg}~Pk -OOA will be called an {η
~Cg}~Pk -OOC. Each such g-cycle will be expressed
with its successive composing vertices expressed between parentheses but without separat-
ing commas, (as is the case for arcs uv and 2-arcs uvw), where as usual the vertex that
succeeds the last vertex of the cycle is its first vertex.
Theorem 3.2. The CDT graphs G of girth = g and AT = k that are not { ~Cg} ~Pk -UH
digraphs are the graphs of Petersen, Heawood, Pappus, Foster and Biggs-Smith. The re-
maining 7 CDT graphs are { ~Cg} ~Pk -UH digraphs.
Proof. Let us consider the case of each CDT graph sequentially. The graph K4 on vertex
set {1, 2, 3, 0} admits the {4 ~C3}~P2 -OOC {(123), (210), (301), (032)}. The graph K3,3
obtained from K6 (with vertex set {1, 2, 3, 4, 5, 0}) by deleting the edges of the triangles
(1, 3, 5) and (2, 4, 0) admits the {9 ~C4}~P3 -OOC {(1234), (3210), (4325), (1430), (2145),
(0125), (5230), (0345), (5410)}. The graph Q3 with vertex set {0, . . . , 7} and edge set
{01, 23, 45, 67, 02, 13, 46, 57, 04, 15, 26, 37} admits the {6 ~C4}~P2 -OOC {(0132), (1045),
(3157), (2376), (0264), (4675)}.
The Petersen graph Pet is obtained from the disjoint union of the 5-cycles µ∞ = (u0u1u2
u3u4) and ν∞ = (v0v2v4v1v3) by the addition of the edges (ux, vx), for x ∈ Z5. Apart
from the two 5-cycles given above, the other 10 5-cycles of Pet can be denoted by µx =
(ux−1uxux+1vx+1vx−1) and νx = (vx−2vxvx+2ux+2ux−2), for each x ∈ Z5. Then,
the following sequence of alternating 5-cycles and 2-arcs starts and ends up with opposite
orientations:
µ2− u3u2u1 µ
∞
+ u0u1u2 µ
1
− u2v2v0 ν
0
− v3u3u2 µ
2
+,
where the subindexes ± indicate either a forward or backward selection of orientation and
each 2-path is presented with the orientation of the previously cited 5-cycle but must be
present in the next 5-cycle with its orientation reversed. Thus Pet cannot be a {~C5}~P3 -UH
digraph.
Another way to see this is via the auxiliary table indicated below, that presents the form
in which the 5-cycles above share the vertex sets of 2-arcs, either O-O or not. The table
details, for each one of the 5-cycles ξ = µ∞, ν∞, µ0, ν0, (expressed as ξ = (ξ0, . . . , ξ4) in
I. J. Dejter: Orienting and separating distance-transitive graphs 225
the shown vertex notation), each 5-cycle η in {µi, νi; i =∞, 0, . . . , 4}\{ξ} that intersects ξ
in the succeeding 2-paths ξiξi+1ξi+2, for i = 0, . . . , 4, with additions involving i taken mod
5. Each such η in the auxiliary table has either a preceding minus sign, if the corresponding
2-arcs in ξ and η are O-O, or a plus sign, otherwise. Each−ηj (resp. ηj) shown in the table
has the subindex j indicating the equality of initial vertices ηj = ξi+2 (resp. ηj = ξi) of
those 2-arcs, for i = 0, . . . , 4:
µ∞:(+µ10,+µ
2
0,+µ
3
0,+µ
4
0,+µ
0
0),
µ0 :(+µ∞4 ,+ν
3
3 ,−ν41 ,−ν14 ,+ν22 ),
ν∞:(+ν20 ,+ν
4
0 ,+ν
1
0 ,+ν
3
0 ,+ν
0
0 ),
ν0 :(+ν∞4 ,−µ12,+µ34,+µ21,−µ43).
This partial auxiliary table is extended to the whole auxiliary table by adding x ∈ Z4
uniformly mod 5 to all superindexes 6=∞, reconfirming that Pet is not {~C5}~P3 -UH.
For each positive integer n, let In stand for the n-vertex cycle (0, 1, . . . , n − 1). The
Heawood graph Hea is obtained from I14 by adding the edges (2x, 5 + 2x), where x ∈
{1, . . . , 7} and operations are in Z14. The 28 6-cycles of Hea include the following 7
6-cycles:
γx=(2x, 2x+1, 2x+2, 2x+3, 2x+4, 2x+ 5), δx=(2x ,2x+5, 2x+6, 2x+7, 2x+8, 2x+13),
x=(2x, 2x+5, 2x+4, 2x+9, 2x+8, 2x+13), ζx=(2x+12, 2x+3, 2x+4, 2x+5, 2x ,2x+13),
where x ∈ Z7. Now, the following sequence of alternating 6-cycles and 3-arcs starts and
ends with opposite orientations for γ0:
γ0+ 2345 γ
1
− 7654 γ
2
+ 6789 γ
3
− ba98 γ
4
+ abcd γ
5
− 10dc γ
6
+ 0123 γ
0
−,
(where tridecimal notation is used, up to d = 13). Thus Hea cannot be a {~C7}~P4 -UH
digraph. Another way to see this is via an auxiliary table for Hea obtained in a fashion
similar to that of the one for Pet above from:
γ0:(+γ62 ,+δ
5
1 ,+γ
1
0 ,+ζ
6
1 ,−
5
1,−ζ
0
4 );
δ0:(+ζ00 ,+γ
2
1 ,−ζ33 ,+δ45 ,+04,+δ33);
0:(+52,−γ
2
4 ,+
2
0,+ζ
4
5 ,+δ
0
4 ,−ζ
6
2 );
ζ0:(+δ00 ,+γ
1
3 ,−15,−δ42 ,−γ05 ,+33).
This reaffirms that Hea is not {~C6}~P4 -UH.
The Pappus graph Pap is obtained from I18 by adding to it the edges (1+6x, 6+6x), (2+
6x, 9 + 6x), (4 + 6x, 11 + 6x), for x ∈ {0, 1, 2}, with sums and products taken mod 18.
The 6-cycles of Pap are expressible as: A0 = (123456), B0 = (3210de), C0 = (34bcde),
D0 = (165gh0), E0 = (329ab4) (where octodecimal notation is used, up to h = 17),
the 6-cycles Ax, Bx, Cx, Dx, Ex obtained by uniformly adding 6x mod 18 to the vertices
of A0, B0, C0, D0, E0, for x ∈ Z3 \ {0}, and F0 = (3298fe), F1 = (hg54ba), F2 =
(167cd0). No orientation assignment makes these cycles into an {18 ~C6}~P3 -OOC, for the
following sequence of alternating 6-cycles and 2-arcs (with orientation reversed between
each preceding 6-cycle to corresponding succeeding 6-cycle) reverses the orientation of its
initial 6-cycle in its terminal one:
D−11 654A0123B0210C1h01D
−1
0 g56C
−1
2 876B
−1
1 789A
−1
1 cbaD2abcA
−1
1 987B
−1
1 678C
−1
2 765D1
=(654bc7) 654 (123456) 123 (3210de) 210 (0129ah)h01 (10hg56) g56 (5gf876) 876
(216789) 789(cba987) cba(d0habc) abc(cba987) 987 (216789) 678 (5gf876) 765(cb4567).
Another way to see this is via an auxiliary table for Pap obtained in a fashion similar to
those above for Pet and Hea, where x = 0, 1, 2 (mod 3):
−Ax:(Bx,Ex ,Ex+2,Dx+1,Dx ,Bx+1);
−Bx:(Ax,Cx+1,F2 ,Ax+2,Cx ,F0 );
−F0:(E0,B1,E1,B2,E2,B0);
−F1:(D0,E2,D1,E0,D2,E1);
−Cx:(Ex,Dx+1,Dx+2,Bx+2,Bx ,Ex+2);
−Dx:(Ax,Cx+2,F1 ,Ax+2,Cx+1,F2 );
−F2:(B1,D1,B2,D2,B0,D0);
−Ex:(F0 ,Cx+1,Ax+1,F1 ,Cx ,Ax ).
226 Ars Math. Contemp. 6 (2013) 221–236
This reaffirms that Pap is not a {~C6}~P3 -UH digraph. In fact, observe that any two 6-cycles
here that share a 2-path possess the same orientation, in total contrast to what happens in
the 7 cases that are being shown to be { ~Cg} ~Pk -UH digraphs, in the course of this proof.
The Desargues graphDes is obtained from the 20-cycle I20, with vertices 4x, 4x+1, 4x+
2, 4x + 3 redenoted alternatively x0, x1, x2, x3, respectively, for x ∈ Z5, by adding the
edges (x3, (x + 2)0) and (x1, (x + 2)2), where operations are mod 5. Then, Des admits
a {20 ~C6}~P3 -OOC formed by the oriented 6-cycles A
x, Bx, Cx, Dx, for x ∈ {0, . . . , 4},
where
Ax=(x0x1x2x3(x+1)0(x+4)3),
Cx=(x2x1x0(x+3)3(x+3)2(x+3)1),
Bx=(x1x0(x+4)3(x+4)2(x+2)1(x+2)2),
Dx=(x0(x+4)3(x+1)0(x+1)1(x+3)2(x+3)3).
The successive copies of ~P3 here, when reversed in each case, must belong to the following
remaining oriented 6-cycles:
Ax:(Cx,Cx+2,Bx+1,Dx+1,Dx ,Bx );
Cx:(Ax,Dx+4,Dx ,Ax+3,Bx+1,Bx+3);
Bx:(Ax,Ax+4,Dx+1,Cx+4,Cx+2,Dx+4);
Dx:(Ax,Cx+1,Bx+1,Bx+4,Cx ,Ax+4);
showing that they constitute effectively an {η ~Cg}~Pk -OOC.
The dodecahedral graph ∆ is a 2-covering graph of the Petersen graph H , where each
vertex ux, (resp., vx), of H is covered by two vertices ax, cx, (resp. bx, dx). A {12 ~C5}~P2 -
OOC of ∆ is given by the oriented 5-cycles (a0a1a2a3a4), (c4c3c2c1c0) and, for each
x ∈ Z5, also by (axdxbx−2dx+1ax+1) and (dxbx+2cx+2cx−2bx−2).
The Tutte 8-cage Tut is obtained from I30, with vertices 6x, 6x+ 1, 6x+ 2, 6x+ 3, 6x+
4, 6x+5 denoted alternatively x0, x1, x2, x3, x4, x5, respectively, for x ∈ Z5, by adding the
edges (x5, (x+ 2)0), (x1, (x+ 1)4) and (x2, (x+ 2)3). Then, Tut admits the {90 ~C8}~P5 -
OOC formed by the oriented 8-cycles:
A0=(4500010203040510),
D0=(3332314443421312),
B0=(4243444510111213),
E0=(4510050441403500),
C0=(0203044140252423),
F 0=(4500354025241110),
G0=(1011242302010045),
J0=(1005040332314445),
H0=(2324111005040302),
K0=(3132030201004544),
I0=(0102030441421314),
L0=(2324253031320302),
M0=(3540410403020100),
P 0=(4544434241040510),
N0=(0001141520213435),
Q0=(4041421314153025),
O0=(4243222134331213),
R0=(0102033231301514),
together with those obtained by adding y ∈ Z5 uniformly mod 5 to all numbers x of
vertices xi in A0, . . . , R0, for each y = 1, 2, 3, 4, yielding in each case oriented 8-cycles
Ay, . . . , Ry .
The Coxeter graph Cox is obtained from three 7-cycles (u1u2u3u4u5u6u0), (v4v6v1v3v5
v0v2), (t3t6t2t5t1t4t0) by adding a copy of K1,3 with degree-1 vertices ux, vx, tx and a
central degree-3 vertex zx, for each x ∈ Z7. Cox admits the {24 ~C7}~P3 -OOC:
{01=(u1u2u3u4u5u6u0),
11=(u1z1v1 v3 z3u3u2),
02=(v1v3v5v0v2v4v6),
12=(z4v4v2v0z0 t0t4),
03=(t1t5t2 t6 t3 t0 t4),
13=(t6t2t5z5u5u6z6),
21=(v5z5u5u4u3 z3 v3),
31=(v5v0z0u0u6 u5 z5),
22=(t6z6v6v4v2 z2t2),
32=(z4t4t1z1v1 v6v4),
23=(u1z1t1t4t0z0u0),
33=(t6t2z2u2u3z3t3),
41=(u1u0z0v0v2 z2 u2),
51=(z4u4u3u2z2 v2 v4),
42=(t6t3z3v3v1v6 z6),
52=(v5v3v1z1t1t5 z5),
43=(z4u4u5z5t5t1t4),
53=(t6z6u6u0z0t0t3),
61=(z4v4v6z6u6 u5 u4),
71=(u1u0u6z6v6 v1 z1),
62=(v5v3z3t3t0 z0v0),
72=(v5z5t5t2z2 v2v0),
63=(u1u2z2t2t5t1z1),
73=(z4t4t0t3z3u3u4)}.
I. J. Dejter: Orienting and separating distance-transitive graphs 227
The Foster graph Fos is obtained from I90, with vertices 6x, 6x+ 1, 6x+ 2, 6x+ 3, 6x+
4, 6x+ 5 denoted alternatively x0, x1, x2, x3, x4, x5, respectively, for x ∈ Z15, by adding
the edges (x4, (x + 2)1), (x0, (x + 2)5) and (x2, (x + 6)3). The 216 10-cycles of Fos
include the following 15 10-cycles, where x ∈ Z15:
φx=(x4x5(x+1)0(x+1)1(x+1)2(x+1)3(x+1)4(x+1)5(x+2)0(x+2)1).
Then, the following sequence of alternating 10-cycles and 4-arcs:
φ0+[14]φ
1
−[31]φ
2
+[34]φ
3
−[51]φ
4
+[54]φ
5
−[71]φ
6
+[74]φ
7
−[91]φ
8
+[94]φ
9
−[b1]φ
a
+[b4]φ
b
−[d1]φ
c
+[d4]φ
d
−[01]φ
e
+[04]
may be continued with φ0−, with opposite orientation to that of the initial φ
0
+, where [xj ]
stands for a 3-arc starting at the vertex xj in the previously cited (to the left) oriented 10-
cycle. Thus Fos cannot be a {~C10}~P5 -UH digraph. Another way to see this is via the
following table of 10-cycles of Fos, where the 10-cycle φ0 intervenes as 10-cycle 00:
00=(04051011121314152021)
10=(00010203042122232425)
80=(02039291747580816463)
90=(0405d0d1d24344452021)
20=(03040510111273749192)
30=(030405d0c5a095949392)
a0=(0405d0d1b4b3b2232221)
b0=(04051035345150452021)
40=(00010263626160553025)
50=(04051035404124232221)
c0=(02030421228382816463)
d0=(03042120455075749192)
60=(03040510353433329392)
70=(0001R203929332313025)
e0=(05103540657095a0c5d0)
f0=(020392933233c2c36263)
where (a) hexadecimal notation of integers is used; (b) the first 14 10-cycles x0, (x =
0, . . . , 13 = d), yield corresponding 10-cycles xj , (j ∈ Z15). via translation modulo 15
of all indexes; and (c) the last two cycles, e0 and f0, yield merely additional 10-cycles
e1, e2, f1 and f2 by the same index translation. A corresponding auxiliary table as in the
discussions for Pet, Hea and Pap above, in which the ± assignments are missing and left
as an exercise for the reader is as follows:
00:(20,4a,11,1e,37,21,89,bc,b0,88)
10:(0e,5d,c0,c9,50,01,6e,9d,92,70)
80:(c7,d0,57,07,06,b4,d0,c0,66,76)
90:(1d,4d,2c,24,34,12,a4,b0,bc,a0)
20:(0e,00,7d,93,d7,c1,c7,d0,9b,60)
30:(6c,d8,e0,59,69,08,66,c9,60,9b)
a0:(9b,db,59,cb,68,72,c9,50,d8,90)
b0:(60,db,93,03,50,72,d0,90,00,50)
40:(7c,cd,76,05,73,52,ee,dd,70,92)
50:(36,4d,be,8b,a6,12,10,a0,88,a0)
c0:(10,28,88,42,a6,16,2e,80,36,a4)
d0:(a4,b0,42,37,b4,a7,80,20,28,89)
60:(36,b0,33,11,39,a7,f3,89,30,20)
70:(49,ad,f3,89,43,22,4c,bd,40,10)
e0:(36,42,39,45,3c,48,30,4b,33,4e)
f0:(70,60,73,63,76,66,79,69,7c,6c)
Let A = (A0, A1, . . ., Ag), D = (D0, D2, . . ., Df ), C = (C0, C4, . . ., Cd), F = (F0, F8,
. . ., F9) be 4 disjoint 17-cycles. Each y = A,D,C, F has vertices yi with i expressed as
an heptadecimal index up to g = 16. We assume that i is advancing in 1,2,4,8 units mod
17, stepwise from left to right, respectively for y = A,D,C, F . Then the Biggs-Smith
graph B-S is obtained by adding to the disjoint union A ∪D ∪ C ∪ F , for each i ∈ Z17,
a 6-vertex tree Ti formed by the edge-disjoint union of paths AiBiCi, DiEiFi, and BiEi,
where the verticesAi,Di, Ci, Fi are already present in the cyclesA,D, C, F , respectively,
and where the vertices Bi and Ei are new and introduced with the purpose of defining the
tree Ti, for 0 ≤ i ≤ g = 16. Now, S has the collection C9 of 9-cycles formed by:
S0=(A0A1B1C1C5C9CdC0B0),
T 0=(C0C4B4A4A3A2A1A0B0),
W 0=(A0A1B1E1F1F9F0E0B0),
X0=(C0C4B4E4D4D2D0E0B0),
U0=(E0F0 F9F1FaF2E2D2D0,)
V 0=(E0D0D2D4D6D8E8F8F0),
Y 0=(E0B0A0A1A2B2E2D2D0),
Z0=(F0 F8 E8B8C8C4C0B0E0),
228 Ars Math. Contemp. 6 (2013) 221–236
and those 9-cycles obtained from these, as Sx, . . . , Zx, by uniformly adding x ∈ Z17 mod
17 to all subindexes i of vertices yi, so that |C9| = 136.
An auxiliary table presenting the form in which the 9-cycles above share the vertex sets of
3-arcs, either O-O or not, is shown below, in a fashion similar to those above for Pet, Hea,
Pap and Fos, where minus signs are set but plus signs are tacit now:
S0:(-T e1 , T 17 ,-Z14 ,Sd4 , S43 ,-Z93 , Td0 ,-T 06 , U08 ),
T 0:( S46 ,-S30 ,-Y 22 , T 14 ,T g3 ,-Y 01 ,-S07 , Sg1 , V 08 ),
W 0:(-U04 ,W 82 ,W 91 ,-U13 ,X27 ,-Xb4 , Y 06 ,-X08 , X95 ),
X0:(-V 04 ,Xf2 ,X21 ,-V 43 ,-W 65 ,W 88 ,-Z08 ,W f4 ,-W 07 ),
U0:(Y g3 ,-U16 ,Z17 ,-W g3 ,-W 00 , Z90 ,-Ug1 , Y 00 , S08),
V 0:(-Zd2 ,-V 46 ,Y 25 ,-Xd3 ,-X00 ,Y 07 ,-V d1 ,-Z05 ,T 08 ),
Y 0:( U07 ,-T 05 ,-T f2 , U10 ,-Y 28 , V f2 ,W 06 , V 05 ,-Y f4 ),
Z0:( U85 ,-Z86 ,-V 40 ,-S85 ,-Sg2 ,-V 07 ,-Z91 , Ug2 ,-X06 ),
This table is extended by adding x ∈ Z17 uniformly mod 17 to all superindexes, confirming
that B-S is not {~C9}~P4 -UH..
4 Separator digraphs of 7 CDT graphs
For each of the 7 CDT graphs G that are { ~Cg} ~Pk -UH digraphs according to Theorem 3,
the following construction yields a corresponding digraph S(G) of outdegree and indegree
two and having underlying cubic graph structure and the same automorphism group of G.
The vertices of S(G) are defined as the (k − 1)-arcs of G. We set an arc in S(G) from
each vertex a1a2 . . . ak−1 into another vertex a2 . . . ak−1ak whenever there is an oriented
g-cycle (a1a2 . . . ak−1ak . . .) in the {η ~Cg}~Pk -OOC provided by Theorem 3 to G. Thus
each oriented g-cycle in the mentioned {η ~Cg}~Pk -OOC yields an oriented g-cycle of S(G).
In addition we set an edge e in S(G) for each transposition of a (k − 1)-arc of G, say
h = a1a2 . . . ak−1, taking it into h−1 = ak−1ak−2 . . . a1. Thus the ends of e are h and
h−1. As usual, the edge e is considered composed by two O-O arcs.
The polyhedral graphsG here are the tetrahedral graphG = K4, the 3-cube graphG = Q3
and the dodecahedral graph G = ∆. The corresponding graphs S(G) have their underly-
ing graphs respectively being the truncated-polyhedral graphs of the corresponding dual-
polyhedral graphs that we can refer as the truncated tetrahedron, the truncated octahedron
and the truncated icosahedron. In fact:
(A) S(K4) has vertices 01, 02, 03, 12, 13, 23, 10, 20, 30, 21, 31, 32; the cycles (123), (210),
(301), (032) of the {η ~Cg}~Pk -OOC of K4 give place to the oriented 3-cycles (12, 23,
31), (21, 10, 02), (30, 01, 13), (03, 32, 20) of S(K4); the additional edges of S(K4) are
(01, 10), (02, 20), (03, 30), (12, 21), (13, 31), (23, 32).
(B) The of oriented cycles of S(Q3) corresponding to the {η ~Cg}~Pk -OOC ofQ3 are (01, 13,
32, 20), (10, 04, 45, 51), (31, 15, 57, 73) ,(23, 37, 76, 62), (02, 26, 64, 40), (46, 67, 75, 54);
the additional edges of S(Q3) are (01, 10), (23, 32), (45, 54), (67, 76), (02, 20), (13, 31),
(46, 64), (57, 75), (04, 40), (15, 51), (26, 62), (37, 73).
(C) The oriented cycles of S(∆) corresponding to the {η ~Cg}~Pk -OOC of ∆ are (a0a1, a1a2,
a2a3, a3a4, a4 a0), (c4c3, c3c2, c2c1, c1c0, c0c4), and both (axdx, dxbx−2, bx−2dx+1, dx+1
ax+1, ax+1ax) and (dxbx+2, bx+2cx+2, cx+2cx−2, cx−2bx−2, bx−2dx), for each x ∈ Z5;
I. J. Dejter: Orienting and separating distance-transitive graphs 229
Figure 1: S(K4), S(Q3) and S(∆)
the additional edges are (axax+1, ax+1ax), (cxcx+1, cx+1cx), (axdx, dx ax), (dxbx+2,
bx+2dx), (bxdx+2, dx+2bx), and (bxcx, cxbx), for each x ∈ Z5.
Among the 7 CDT graphs G that are { ~Cg} ~Pk -UH digraphs, the polyhedral graphs treated
above are exactly those having arc-transitivity k = 2. Figure 1 contains representations of
these graphs S(G), namely S(K4), S(Q3) and S(∆), with the respective 3-cycles, 4-cycles
and 5-cycles in black trace to be considered clockwise oriented, but for the external cycles
in the cases S(Q3) and S(∆), to be considered counterclockwise oriented. The remaining
edges (to be referred as transposition edges) are gray colored and considered bidirectional.
The cycles having alternate black and gray edges here, arising respectively from arcs from
the oriented cycles and from the transposition edges, are 6-cycles. Each such 6-cycle has
its vertices sharing the notation, indicated in gray, of a unique vertex of the corresponding
G. Each vertex of G is used as such gray 6-cycle indication.
The truncated tetrahedron, truncated octahedron and truncated icosahedron, oriented as
indicated for Figure 1, are the Cayley digraphs of the groupsA4, S4 andA5, with respective
generating sets {(123), (12)(34)}, {(1234), (12)} and {(12345), (23)(45)}. Thus
S(K4)≡Cay(A4,{(123),(12)(34)}),S(Q3)≡Cay(S4,{(1234),(12)}),S(∆)≡Cay(A5,{(12345),(23)(45)}).
(D) The oriented cycles of S(K3,3) corresponding to the {η ~Cg}~Pk -OOC of K3,3 are:
(123, 234, 341, 412), (321, 210, 103, 032), (432, 325, 254, 543),
(143, 430, 301, 014), (214, 145, 452, 521), (012, 125, 250, 501),
(523, 230, 305, 052), (034, 345, 450, 503), (541, 410, 105, 054);
and additional edges of S(K3,3) are:
(123, 321), (234, 432), (341, 143), (412, 214), (210, 012), (103, 301),
(032, 230), (325, 523), (254, 452), (543, 345), (430, 034), (014, 410),
(145, 541), (521, 125), (250, 052), (501, 105), (305, 503), (450, 054).
230 Ars Math. Contemp. 6 (2013) 221–236
Figure 2: S(K3,3)
A cut-out toroidal representation of S(K3,3) is in Figure 2, where black-traced 4-cycles
are considered oriented clockwise, corresponding to the oriented 4-cycles in the {η ~Cg}~Pk -
OOC of K3,3, and where gray edges represent transposition edges of S(K3,3), which gives
place to the alternate 8-cycles, constituted each by an alternation of 4 transposition edges
and 4 arcs of the oriented 4-cycles. In S(K3,3), there are 9 4-cycles and 9 8-cycles. Now,
the group < (0, 5, 4, 1)(2, 3), (0, 2)(1, 5) > has order 36 and acts regularly on the vertices
of S(K3,3). For example, (0, 2)(1, 5) stabilizes the edge (145, 541), and the permuta-
tion (0, 5, 4, 1)(2, 3) permutes (clockwise) the black oriented 4-cycle (541, 410, 105, 054).
Thus S(K3,3) is a Cayley digraph. Also, observe the oriented 9-cycles in S(K3,3) obtained
by traversing alternatively 2-arcs in the oriented 4-cycles and transposition edges; there are
6 such oriented 9-cycles.
(E) The collection of oriented cycles of S(Des) corresponding to the {η ~Cg}~Pk -OOC of
Des is formed by the following oriented 6-cycles, where x ∈ Z5:
(x0x1x2, x1x2x3, x2x3x
1
0, x3x
1
0x
4
3, x
1
0x
4
3x0, x
4
3x0x1),
(x1x0x43, x0x
4
3x
4
2, x
4
3x
4
2x
2
1, x
4
2x
2
1x
2
2, x
2
1x
2
2x1, x
2
2x1x0),
(x2x1x0, x1x0x
3
3, x0x
3
3x
3
2, x
3
3x
3
2x
3
1, x
3
2x
3
1x2, x
3
1x2x1),
(x0x43x
1
0, x
4
3x
1
0x
1
1, x
1
0x
1
1x
3
2, x
1
1x
3
2x
3
3, x
3
2x
3
3x0, x
3
3x0x
4
3),
respectively for the 6-cycles Ax, Bx, Cx, Dx, where xji stands for (x + j)i; each of the
participant vertices here is an end of a transposition edge. Figure 3 represents a subgraph
S(M3) of S(Des) associated with the matching M3 of Des indicated in its representation
“inside” the left-upper “eye” of the figure, where vigesimal integer notation is used (up
to j = 19); in the figure, additional intermittent edges were added that form 12 square
pyramids, 4 such edges departing from a corresponding extra vertex; so, 12 extra vertices
appear that can be seen as the vertices of a cuboctahedron whose edges are 3-paths with
inner edge in S(M3) and intermittent outer edges. There is a total of 5 matchings, like
M3, that we denote Mx, where x = 3, 7, b, f, j. In fact, S(Des) is obtained as the union⋃
{S(Mx);x = 3, 7, b, f, j}. Observe that the components of the subgraph induced by the
matchingMx inDes are at mutual distance 2 and thatMx can be divided into three pairs of
edges with the ends of each pair at minimum distance 4, facts that can be used to establish
the properties of S(Des).
I. J. Dejter: Orienting and separating distance-transitive graphs 231
Figure 3: M3 and the subgraph of S(Des) associated to it
232 Ars Math. Contemp. 6 (2013) 221–236
In Figure 3 there are: 12 oriented 6-cycles (dark-gray interiors); 6 alternate 8-cycles (thick-
black edges); and 8 9-cycles with alternate 2-arcs and transposition edges (light-gray inte-
riors). The 6-cycles are denoted by means of the associated oriented 6-cycles ofDes. Each
9-cycle has its vertices sharing the notation of a vertex of V (Des) and this is used to denote
it. Each edge e in M3 has associated a closed walk in Des containing every 3-path with
central edge e; this walk can be used to determine a unique alternate 8-cycle in S(M3),
and viceversa. Each 6-cycle has two opposite (black) vertices of degree two in S(M3). In
all, S(Des) contains 120 vertices; 360 arcs amounting to 120 arcs in oriented 6-cycles and
120 transposition edges; 20 dark-gray 6-cycles; 30 alternate 8-cycles; and 20 light-gray
9-cycles. By filling the 6-cycles and 8-cycles here with 2-dimensional faces, then the 120
vertices, 180 edges (of the underlying cubic graph) and resulting 20 + 30 = 50 faces yield
a surface of Euler characteristic 120 − 180 + 50 = −10, so this surface genus is 6. The
automorphism group of Des is G = S5 × Z2. Now, G contains three subgroups of index
2: two isomorphic to to S5 and one isomorphic to A5 × Z2. One of the two subgroups of
G isomorphic to S5 (the diagonal copy) acts regularly on the vertices of S(Des) and hence
S(Des) is a Cayley digraph.
(F) The collection of oriented cycles of S(Cox) corresponding to the {η ~Cg}~Pk -OOC of
Cox is formed by oriented 7-cycles, such as:
01 = (u1u2u3, u2u3u4, u3u4u5, u4u5u6, u5u6u0, u6u0u1, u0u1u2),
and so on for the remaining oriented 7-cycles xy with x ∈ {0, . . . , 7} and y ∈ {1, 2, 3},
based on the corresponding table in the proof of Theorem 3. Moreover, each vertex of
S(Cox) is adjacent via a transposition edge to its reversal vertex. Thus S(Cox) has: under-
lying cubic graph; indegree = outdegree = 2; 168 vertices; 168 arcs in 24 oriented 7-cycles;
84 transposition edges; and 42 alternate 8-cycles. Its underlying cubic graph has 252 edges.
From this information, by filling the 7- and 8-cycles mentioned above with 2-dimensional
faces, we obtain a surface with Euler characteristic 168 − 252 + (24 + 42) = −18, so its
genus is 10. On the other hand, S(Cox) is the Cayley digraph of the automorphism group
of the Fano plane, namely PSL(2, 7) = GL(3, 2) [4], of order 168, with a generating set
of two elements, of order 2 and 7, representable by the 3×3-matrices (100, 001, 010)T and
(001, 101, 010)T over the field F2, where T stands for transpose.
Figure 4 depicts a subgraph of S(Cox) containing in its center a (twisted) alternate 8-cycle
that we denote (in gray) z1u1, and, around it, four oriented 7-cycles adjacent to it, (namely
11, 71, 23, 63, denoted by their corresponding oriented 7-cycles in Cox, also in gray),
plus four additional oriented 7-cycles (namely 00, 32, 41, 52), related to four 9-cycles
mentioned below. Black edges represent arcs, and the orientation of these 8 7-cycles is
taken clockwise, with only gray edges representing transposition edges of S(Cox). Each
edge of Cox determines an alternate 8-cycle of S(Cox). In fact, Figure 4 contains not
only the alternate 8-cycle corresponding to the edge z1u1 mentioned above, but also those
corresponding to the edges u1u2, v1z1, t1z1 and u0u1. These 8-cycles and the 7-cycles in
the figure show that alternate 8-cycles C and C ′ adjacent to a particular alternate 8-cycle
C ′′ in S(Cox) on opposite edges e and e′ of C ′′ have the same opposite edge e′′ both to
e and e′ in C and C ′, respectively. There are two instances of this property in Figure 4,
where the two edges taking the place of e′′ are the large central diagonal gray ones, with
C ′′ corresponding to u1z1. As in (E) above, the fact that each edge e of Cox determines
I. J. Dejter: Orienting and separating distance-transitive graphs 233
Figure 4: A subdigraph of S(Cox) associated with an edge of Cox
an alternate 8-cycle of S(Cox) is related with the closed walk that covers all the 3-paths
having e as central edge, and the digraph S(Cox) contains 9-cycles that alternate 2-arcs in
the oriented 7-cycles with transposition edges. In the case of Figure 4, these 9-cycles are,
in terms of the orientation of the 7-cycles:
(u2u1z1, u1z1v1, z1v1v3, v3v1z1, v1z1t1, z1t1t5, t5t1z1, t1z1u1, z1u1u2),
(v1z1u1,z1u1u0,u1u0u6,u6u0u1,u0u1u2,u1u2u3,u3u2u1,u2u1z1,u1z1v1),
(u0u1z1, u1z1t1, z1t1t4, t4t1z1, t1z1v1, z1v1v6, v6v1z1, v1z1u1, z1u1u0),
(t1z1u1,z1u1u2,u1u2z2,z2u2u1,u2u1u0,u1u0z0,z0u0u1,u0u1z1,u1z1t1).
A convenient description of alternate 8-cycles, as those denoted in gray in Figure 4 by the
edges z1u1, z1v1, u2u1, u0u1, z1t1 of Cox, is given by indicating the successive passages
through arcs of the oriented 7-cycles, with indications by means of successive subindexes
in the order of presentation of their composing vertices, which for those 5 alternate 8-cycles
looks like:
(1160,7
1
56,2
3
60,6
3
56), (5
2
12,3
2
23,7
1
45,1
1
01), (0
1
01,1
1
56,6
3
60,4
1
56), (2
3
56,7
1
60,0
0
56,4
1
60), (3
2
12,5
2
23,6
3
45,2
3
01).
In a similar fashion, the four bi-alternate 9-cycles displayed just above can be presented by
means of the shorter expressions:
(1161,5
2
13,6
3
46), (7
1
50,0
1
50,1
1
50), (2
3
61,3
2
13,7
1
46), (6
3
50,4
1
50,2
3
50).
By the same token, there are twenty four tri-alternate 28-cycles, one of which is expressible
as:
(0103,6
1
03,3
2
40,2
3
36,5
3
36,4
2
62,1
1
40).
234 Ars Math. Contemp. 6 (2013) 221–236
At this point, we observe that S(K4), S(Q3) and S(∆) have alternate 6-cycles, while
S(K3,3), S(Des) and S(Cox) have alternate 8-cycles.
(G) The collection of oriented cycles of S(Tut) corresponding to the {η ~Cg}~Pk -OOC of
Tut is formed by oriented 8-cycles, such as: A0 =
(4500010203, 0001020304, 0102030405, 0203040510, 0304051045, 0405104500, 0510450001, 1045000102)
and so on for the remaining oriented 8-cycles Xy with X ∈ {A, . . . , R} and y ∈ Z5 based
on the corresponding table in the proof of Theorem 3. Moreover, each vertex of S(Tut)
is adjacent via a transposition edge to its reversal vertex. Thus S(Tut) has: underlying
cubic graph; indegree = outdegree = 2; 720 vertices; 720 arcs in 90 oriented 8-cycles;
360 transposition edges; and 180 alternate 8-cycles, (36 of which are displayed below); its
underlying cubic graph has 1080 edges. From this information, by filling the 900 8-cycles
above with 2-dimensional faces, a surface with Euler characteristic 720 − 1080 + 240 =
−120 is obtained, so genus = 61. On the other hand, the automorphism group of Tut is the
projective semilinear group G = PΓL(2, 9) [13], namely the group of collineations of the
projective line PG(1, 9). The group G contains exactly three subgroups of index 2 (and so
of order 720), one of which (namely M10, the Mathieu group of order 10, acts regularly on
the vertices of S(Tut). Thus S(Tut) is a Cayley digraph.
A fifth of the 180 alternate 8-cycles of S(Tut) can be described by presenting in each
case the successive pairs of vertices in each oriented 8-cycle Xy as follows, each such pair
denoted by means of the notation Xyu(u+1) , where u stands for the 4-arc in position u in
Xy , with 0 indicating the first position:
(A001,
(A034,
M034,
J070,
B434,
L370,
K012)
H023)
(A012,
(A045,
P 101,
E070,
I070,
P 045,
M023)
J067)
(A023,
(A056,
H034,
E145,
B170,
F 170,
P 170)
E067)
(A067,
(B012,
G045,
R334,
M167,
N156,
E134)
C223)
(A070,
(B023,
K023,
M145,
L212,
Q267,
G034)
R323)
(B001,
(B045,
C234,
D367,
Q323,
R170,
P 067)
K101)
(B056,
(C012,
D034,
N467,
O056,
F 345,
D356)
G367)
(B067,
(C045,
H445,
L067,
C467,
J201,
D023)
Q112)
(C001,
(C056,
G370,
H056,
H370,
O434,
M001)
L056)
(C070,
(D070,
M012,
I367,
I001,
P 412,
D112)
R367)
(D001,
(E001,
I412,
N401,
O112,
K145,
I356)
P 034)
(D045,
(E012,
O267,
N234,
L145,
F 334,
O045)
N470)
(E023,
(F 023,
M070,
N445,
H301,
R145,
N223)
J345)
(E056,
(F 056,
F 101,
Q256,
Q245,
M156,
F 067)
G056)
(F 012,
(G001,
J356,
I145,
P 356,
O423,
Q134)
H067)
(G012,
(I023,
Q101,
J123,
J212,
K167,
I134)
O201)
(G023,
(J034,
L223,
R356,
R212,
P 423,
Q170)
K056)
(H012,
(K070,
L301,
R001,
K134,
L034,
N412)
O170)
Again, as in the previously treated cases, we may consider the oriented paths that alter-
natively traverse two arcs in an oriented 8-cycle and then a transposition edge, repeating
this operation until a closed path is formed. It happens that all such bi-alternate cycles are
12-cycles. For example with a notation akin to the one in the last table, we display the first
row of the corresponding table of 12-cycles:
(A002,
(......,
P 102,
......,
R060,
......,
K002)
......)
(A013,
(......,
H035,
......,
C060,
......,
M013)
......)
(A024,
(......,
J071,
......,
Q413,
......,
P 160)
......)
As in the case of the alternate 8-cycles above, which are 180, there are 180 bi-alternate
12-cycles in S(Tut). On the other hand, an example of a tri-alternate 32-cycle in S(Tut)
is given by:
(A003, H
0
36, O
4
36, D
2
50, I
0
61, D
1
14, O
1
50, K
0
72).
I. J. Dejter: Orienting and separating distance-transitive graphs 235
There is a total of 90 such 32-cycles. Finally, an example of a tetra-alternate 15-cycle in
S(Tut) is given by (A004, J073,K062), and there is a total of 240 such 15-cycles. More can
be said about the relative structure of all these types of cycles in S(Tut).
The automorphism groups of the graphs S(G) in items (A)-(G) above coincide with those
of the corresponding graphs G because the construction of S(G) depends solely on the
structure of G as analyzed in Section 3 above. Salient properties of the graphs S(G) are
contained in the following statement.
Theorem 4.1. For each CDT graph that is a { ~Cg} ~Pk -UH digraph, S(G) is: (a) a vertex-
transitive digraph with indegree = outdegree = 2, underlying cubic graph and the auto-
morphism group of G; (b) a { ~Cg, ~C2}-ultrahomogeneous digraph, where ~Cg stands for
oriented g-cycle coincident with its induced subdigraph and each vertex is the intersec-
tion of exactly one such ~Cg and one ~C2; (c) a Cayley digraph. Moreover, the following
additional properties hold, where s(G) = subjacent undirected graph of S(G):
(A) S(K4) ≡ Cay(A4, {(123), (12)(34)}), s(K4) = truncated octahedron;
(B) S(Q3) ≡ Cay(S4, {(1234), (12)}), s(Q3) = truncated octahedron;
(C) S(∆) ≡ Cay(A5, {(12345), (23)(45)}), s(∆) = truncated icosahedron;
(D) S(K3,3) is the Cayley digraph of the subgroup of S6 on the vertex set {0, 1, 2, 3, 4, 5}
generated by (0, 5, 4, 1)(2, 3) and (0, 2)(1, 5) and has a toroidal embedding whose
faces are delimited by 9 oriented 4-cycles and 9 alternate 8-cycles;
(E) S(Des) is the Cayley digraph of a diagonal copy of S5 in the automorphism group
S5 × Z2 of Des and has a 6-toroidal embedding whose faces are delimited by 20
oriented 6-cycles and 30 alternate 8-cycles;
(F) S(Cox) ≡ Cay(GL(3, 2), {(100, 001, 010)T , (001, 101, 010)T }), has a 10-toroidal
embedding whose faces are delimited by 24 oriented 7-cycles and 42 alternate 8-
cycles;
(G) S(Tut) is the Cayley digraph of a subgroup M10 of order 2 in the automorphism
group PΓL(2, 9) of Tut and has a 61-toroidal embedding whose faces are delimited
by 90 oriented 8-cycles and 180 alternate 8-cycles.
Corollary 4.2. The bi-alternate cycles in the graphs S(G) above are 9-cycles unless either
G = Q3 or G = ∆, in which cases they are respectively 12-cycles and 15-cycles.
Acknowledgement
The author is grateful to the referee of a previous version of this paper for indications and
corrections that lead to the present manuscript and for encouragement with respect to the
value of the construction of the 7 directed graphs S(G) in Section 4.
References
[1] N. L. Biggs, Algebraic Graph Theory (2nd ed.), Cambridge University Press, 1993.
[2] B. Mohar and C. Thomassen, Graphs on surfaces, Johns Hopkins Univ. Press, 2001.
236 Ars Math. Contemp. 6 (2013) 221–236
[3] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance–Regular Graphs, Springer-Verlag,
New York 1989.
[4] E. Brown and N. Loehr, Why is PSL(2, 7) = GL(3, 2)?, Amer. Math. Mo. 116-8 (2009),
727–732.
[5] P. J. Cameron, 6-transitive graphs, J. Combin. Theory Ser. B 28 (1980), 168–179.
[6] G. L. Cherlin, The Classification of Countable Homogeneous Directed Graphs and Countable
Homogeneous n-tournaments, Memoirs Amer. Math. Soc., vol. 131, number 612, Providence
RI, January 1988.
[7] A. Devillers, Classification of some homogeneous and ultrahomogeneous structures, Dr. Sc.
Thesis, Université Libre de Bruxelles, 2001–2002.
[8] R. Fraı̈ssé, Sur l’extension aux relations de quelques proprietés des ordres, Ann. Sci. École
Norm. Sup. 71 (1954), 363–388.
[9] A. Gardiner, Homogeneous graphs, J. Combin. Theory Ser. B 20 (1976), 94–102.
[10] C. Godsil and G. Royle, Algebraic Graph Theory, Springer–Verlag, 2001.
[11] Ja. Ju. Gol’fand and M. H. Klin, On k-homogeneous graphs, Algorithmic studies in combina-
torics 186 (1978), 76–85, in Russian.
[12] J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley Interscience, 1987.
[13] J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Oxford Science Publications, 2nd
ed., Clarendom Press, Oxford 1998.
[14] D. C. Isaksen, C. Jankowski and S. Proctor, On K∗-ultrahomogeneous graphs, Ars Combina-
toria 82 (2007), 83–96.
[15] I. A. Faradzev, A. A. Ivanov, M. Klin et al., The Algebraic Theory of Combinatorial Objects,
Math. Appl. (Soviet Series), 84, Dordrecht, Kluwer, 1992.
[16] A. H. Lachlan and R. Woodrow, Countable ultrahomogeneous undirected graphs, Trans. Amer.
Math. Soc. 262 (1980), 51–94.
[17] C. Ronse, On homogeneous graphs, J. London Math. Soc. 17 (1978), 375–379.
[18] B. I. Rose and R. E. Woodrow, Ultrahomogeneous structures, Mathematical Logic Quarterly
27 (1981), 23–30.
[19] J. Sheehan, Smoothly embeddable subgraphs, J. London Math. Soc. 9 (1974), 212–218.
[20] A. T. White, Graphs of groups on surfaces, North-Holland, Mathematics Studies 188, 2001.