On a {K_4,K_{2,2,2}}-ultrahomogeneous graph
On a {K4, K2,2,2}-ultrahomogeneous graph
Italo J. Dejter
University of Puerto Rico
Rio Piedras, PR 00931-3355
ijdejter@uprrp.edu
Abstract
The existence of a connected 12-regular {K4,K2,2,2}-ultrahomogeneous graph G is
established, (i.e. each isomorphism between two copies of K4 or K2,2,2 in G extends to
an automorphism of G), with the 42 ordered lines of the Fano plane taken as vertices.
This graph G can be expressed in a unique way both as the edge-disjoint union of
42 induced copies of K4 and as the edge-disjoint union of 21 induced copies of K2,2,2,
with no more copies of K4 or K2,2,2 existing in G. Moreover, each edge of G is shared
by exactly one copy of K4 and one of K2,2,2. While the line graphs of d-cubes, (3 ≤
d ∈ ZZ), are {Kd,K2,2}-ultrahomogeneous, G is not even line-graphical. In addition,
the chordless 6-cycles of G are seen to play an interesting role and some self-dual
configurations associated to G with 2-arc-transitive, arc-transitive and semisymmetric
Levi graphs are considered.
1 Introduction
Let H be a connected regular graph and let m,n ∈ ZZ with 1 < m < n. An {H}mn -graph is a
connected graph that: (a) is representable as an edge-disjoint union of n induced copies of
H ; (b) has exactly m copies of H incident to each vertex, with no two such copies sharing
more than one vertex; and (c) has exactly n copies of H as induced subgraphs isomorphic
to H .
We remark that an {H}mn -graph G is {H}-ultrahomogeneous (as in [7]) if every isomor-
phism between two copies of H in G extends to an automorphism of G. Graph ultrahomo-
geneity is a concept that can be traced back to [9, 6, 8].
Notice that a connected graph G is m-regular if and only if it is a {K2}
|E(G)|-graph.
In this case, G is arc-transitive if and only if G is {K2}-ultrahomogeneous. Thus, {H}-
ultrahomogeneity is a notion of graph symmetry stronger than arc-transitivity.
If G is an {Hi}
-graph, where i = 1, 2, and H1 6= H2, then G is said to be an
-graph. If, in addition, G is {Hi}-ultrahomogeneous, for both i = 1, 2, then
G is {H1, H2}-ultrahomogeneous, again as in [7]. If each edge of G is in exactly one copy
of Hi, for both i = 1, 2, then G is said to be fastened. If min(m1, m2) = m1 = 2 and
http://arxiv.org/abs/0704.1493v3
H1 is a complete graph, then G is said to be line-graphical. For example, the line graph
of the d-cube, where 3 ≤ d ∈ ZZ, is a line-graphical fastened {Kd, K2,2}-ultrahomogeneous
{K2,2}
d(d−1)2d−3
-graph. The first case here, known as the cuboctahedron, is a fastened
{K3, K2,2, C6}-ultrahomogeneous {K3}
8{K2,2}
6{C6}
4-graph, where C6 is 6-cycle.
In Sections 3-5, a 12-regular fastened {K4, K2,2,2}-ultrahomogeneous {K4}
42{K2,2,2}
graph G of order 42 and diameter 3 is presented. The role that d-cliques Kd and squares
K2,2 play in the line graph of the d-cube is performed in G by tetrahedra K4 and octahedra
K2,2,2, but in this case with min(m1, m2) =min(4, 3) > 2, so G is non-line-graphical.
The graph G has automorphism-group order |A(G)| = 1008 = 4|E(G)|. In Section 5, the
252 edges of G can be seen as the left cosets of a subgroup Γ ⊂ A(G) of order 4, and its
vertices as the left cosets of a subgroup of A(G) of order 24.
These two equivalence classes of subgraphs of G, i.e. tetrahedra and octahedra, allow
in Section 6 to define several combinatorial configurations ([3]) related to G, 3 of which
are self-dual, with their Levi graphs as: (1) a 4-regular 2-arc-transitive graph ([2]) on 84
vertices and 1008 automorphisms, with diameter = girth = 6, reflecting a natural duality
property of G; (2) an 8-regular arc-transitive graph on 42 vertices and 2016 automorphisms,
with diameter = 3 and girth = 4; and (3) a 6-regular semisymmetric graph ([5]) on 336
vertices and 1008 automorphisms, with diameter = girth = 6 and just two slightly differing
distance distributions. The Menger graph and dual Menger graph associated to this Levi
graph have common degree 24 and diameter = girth = 3, with 1008 and 2016 automorphisms,
respectively.
Section 7 distinguishes the k-holes (or chordless k-cycles) of G with the least k > 4,
namely k = 6, and studies their participation in some toroidal subgraphs of G that together
with the octahedra of G can be filled up to form a closed piecewise linear 3-manifold.
After some considerations on the Fano plane, we pass to define G and study its properties.
2 Ordered Fano pencils
The Fano plane F is the (73)-configuration with points 1,2,3,4,5,6,7 and Fano lines 123, 145,
167, 246, 257, 347, 356. The map Φ that sends the points 1, 2, 3, 4, 5, 6, 7 respectively onto
the lines 123, 145, 167, 246, 257, 347, 356 has the following duality properties: (1) each
point p of F pertains to the lines Φ(q), where q ∈ Φ(p); (2) each Fano line ℓ contains the
points Φ(k), where k runs over the lines passing through Φ(ℓ).
Given a point p of F , the collection of lines through p is a pencil of F . A linearly ordered
presentation of these lines is an ordered pencil through p. An ordered pencil v through p is
denoted v = (p, qara, qbrb, qcrc), orderly composed, in reality, by the lines pqara, pqbrb, pqcrc.
Note that there are 3! = 6 ordered pencils through any point p of F .
3 The {K4, K2,2,2}-ultrahomogeneous graph G
Ordered pencils constitute the vertex set of our claimed graph G, with any two vertices
v = (p, qara, qbrb, qcrc) and v
′ = (p′, q′ar
c) adjacent whenever the following two
conditions hold: (1) p 6= p′; (2) |piri ∩ p
i| = 1, for i = a, b, c. The 3 points of intersection
resulting from item (2) form a Fano line, which we consider as an ordered Fano line by taking
into account the subindex order a < b < c, and as such, set it as the strong color of the edge
vv′. This provides G with an edge-coloring.
An alternate definition of G can be given via Φ−1, in which the vertices of G can be
seen as the ordered Fano lines xaxbxc, with any two such vertices adjacent if their associated
Fano lines share the entry in F of exactly one of its 3 positions, either a or b or c. We keep
throughout, however, the ordered-pencil presentation of G, but the first self-dual configura-
tion of Subsection 6.1 and accompanying example show that the suggested dual presentation
of G is valid as well.
Notice that the vertices of G with initial entry p = 1 appear in lexicographic order as:
(1, 23, 45, 67), (1, 23, 67, 45), (1, 45, 23, 67), (1, 45, 67, 23), (1, 67, 23, 45), (1, 67, 45, 23),
which may be simplified in notation by using super-indices a through f to denote the shown
order, that is: 1a, 1b, 1c, 1d, 1e, 1f , respectively. A similar lexicographic presentation may be
given to the vertices of G having p = 2, . . . , 7. This treatment covers the 42 vertices of G.
As an example of the adjacency of G, the neighbors of 1a = (1, 23, 45, 67) in G are:
(2, 13, 46, 57), (2, 13, 57, 46), (3, 12, 47, 56), (3, 12, 56, 47),
(4, 26, 15, 37), (4, 37, 15, 26), (5, 27, 14, 36), (5, 36, 14, 27),
(6, 24, 35, 17), (6, 35, 24, 17), (7, 25, 34, 16), (7, 34, 25, 16),
or in the continuation of the simplified notation above: 2a, 2b, 3a, 3b, 4c, 4e, 5c, 5e, 6d, 6f , 7d, 7f .
The strong colors of the resulting edges are: 167, 154, 176, 154, 356, 246, 347, 451, 321, 231,
321, respectively.
Given vertices v = (p, qara, qbrb, qcrc) and w = (p
′, q′ar
c) adjacent in G, there
exists a well-defined j ∈ {a, b, c} such that (1) p ∈ q′jr
j; (2) p
′ ∈ qjrj ; (3) the lines pqjrj and
p′q′jr
j intersect at either qj or rj , which coincides with either q
j or r
j. Say that these lines
pqjrj and p
′q′jr
j intersect at qj . Then qj (including the subindex j) is taken as the weak color
for the edge vw. This provides G with another edge-coloring, with symbols qj, where q ∈ F
and j ∈ {a, b, c}. For example, the weak colors qj corresponding to the 12 edges incident to
1a, as cited above, are: 3a, 3a, 2a, 2a, 5b, 5b, 4b, 4b, 7c, 7c, 6c, 6c, respectively.
3.1 The automorphism group A(G) of G
The 12 neighbors of 1a displayed above induce a subgraph NG(1
a) of G, called the open
neighborhood of 1a in G, which is isomorphic to the graph Λ of the hemi-rhombicubocta-
hedron (obtained from the rhombicuboctahedron by identification of antipodal vertices and
edges). This is a 4-regular vertex-transitive graph on 12 vertices embedded in the projective
plane with 13 faces realized by 4 disjoint triangles and 9 additional 4-holes. The 4-holes are
of two types: (1) 6 have two opposite sides adjacent each to a triangle; (2) the other 3 have
only their vertices in common with the 4 triangles. We also have the graph homomorphism
f : Λ → K4 of Figure 1, where f(ji) = i for i ∈ {0, 1, 2, 3}, j ∈ {a, b, c} and Λ is depicted
in two different ways inside (dotted) fundamental polygons of the real projective plane.
❜ ❜❜ ❜
b0❜ ❜
b0 b2
2 3❜ ❜
Figure 1: The homomorphism f : Λ → K4 with f(ji) = i for i ∈ {0, 1, 2, 3}, j ∈ {a, b, c}
Moreover, we may identify Λ with NG(1
a) via a graph isomorphism g : Λ → NG(1
a) given
g(a0) = 5
c, g(a1) = 4
c, g(a2) = 5
e, g(a3) = 4
g(b0) = 6
d, g(b1) = 7
d, g(b2) = 7
f , g(b3) = 6
g(c0) = 2
b, g(c1) = 2
a, g(c2) = 3
b, g(c3) = 3
Moreover, the graph homomorphism f induces, at the level of automorphism groups of
graphs, a group isomorphism f ∗ : A(Λ) → A(K4) = S4. In fact, f
∗ is given by sending
the following generators of A(Λ) into corresponding generators of S4 (that can be better
visualized from the leftmost Λ to the rightmost K4 depicted in Figure 1):
(a1b2c3)(b1c2a3)(c1a2b3)(a0b0c0) → (123),
(a0a1)(a2a3)(b0b1)(b2b3)(c0c1)(c2c3) → (01)(23),
(a0a1a2a3)(c0b1c2b3)(b0c1b2c3) → (0123).
Thus, A(NG(1
a)) = A(Λ) = S4 has 24 elements, which is consistent with the size of a
vertex stabilizer of G. Furthermore, since G has 42 vertices that behave exactly in the same
geometric way as ordered pencils in F , we conclude that |A(G)| = 42× 24 = 1008.
4 Copies of K2,2,2 and K4 in G
Notice that f maps bijectively the 3 4-cycles and 4 triangles of K4 respectively onto the 3
4-holes of Λ of type (2) above and the 4 triangles of Λ. Notice also that these 7 holes form
a cycle-decomposition of Λ. Inside the closed neighborhood NG[w] of each vertex w of G
(induced in G by w and the open neighborhood NG(w)), we obtain 3 copies of K2,2,2 and 4
copies of K4, which are induced by w together respectively with the mentioned 3 4-holes and
4 triangles. Observe that these 7 induced subgraphs of G have intersection formed solely by
w. The rest of this section is dedicated to the study of these polyhedral subgraphs.
First, notice that the inverse image f−1 of each edge of K4 is one of the 6 4-holes of Λ of
type (1) above. This yields another cycle-decomposition of Λ, which in turn makes explicit
the remaining 4-holes of G, apart from the 4-holes contained in the copies of K2,2,2 of G.
However, these new 4-holes are not contained in any copy of K2,2,2 in G.
4.1 Copies of K2,2,2 in G
Each vertex of G belongs to 3 induced copies of K2,2,2 in G. For example, the sets of
weak colors qj of the edges of such copies for the vertex 1
a, that contain the 4-holes
g(c0, c2, c1, c3), g(a0, a1, a2, a3) and g(b0, b1, b3, b2) arising in Subsection 3.1, are respectively:
{1a, 2a, 3a}, {1b, 4b, 5b}, {1c, 6c, 7c}.
Each qj colors the edges of a specific 4-hole in its corresponding copy of K2,2,2. The 3
weak colors appearing in each copy of K2,2,2 correspond bijectively with its 3 4-holes, the
edges of each 4-hole bearing a common weak color of its own.
A similar situation holds for any other vertex of G. There is a copy of K2,2,2 in G whose
set of weak colors of edges is {xj , yj, zj}, for each line xyz of F and index j ∈ {a, b, c}. We
denote this copy of K2,2,2 by [xyz]j . As a result, there is a total of 21 = 7 × 3 copies of
K2,2,2 in G. In fact, triangles with weak colors qj sharing a common j (but q varying) are
only present in the said copies of K2,2,2 in G. Each 4-hole in a copy of K2,2,2 in G have: (1)
edges sharing a common weak color qj and (2) opposite vertices representing ordered pencils
through a common point of F , which yields a total of two such points per 4-hole.
For example, the strong colors of the triangles [xyz]j composing the copies of K2,2,2
incident to 1a conform triples of strong colors having:
for [123]a, a-entries covering line 123, and another fixed entry equal to each one of 4,5,6,7:
(145, 246, 347), (154, 257, 356), (167, 257, 347), (176, 275, 374),
(154, 264, 374), (145, 275, 365), (176, 275, 374), (167, 246, 365);
for [145]b, b-entries covering line 145, and another fixed entry equal to each one of 2,3,6,7:
(213, 246, 257), (312, 347, 356), (617, 642, 653), (716, 743, 752),
(312, 642, 752), (213, 743, 653), (716, 246, 356), (617, 347, 257);
for [167]c, c-entries covering line 167, and another fixed entry equal to each one of 2,3,4,5:
(231, 246, 257), (321, 356, 347), (451, 426, 437), (541, 536, 527),
(321, 426, 527), (231, 536, 437), (541, 246, 347), (451, 356, 257).
In fact, these triangles are respectively:
(2a, 3a, 1a), (2b, 3b, 1a), (2a, 3b, 1a), (2b, 3a, 1a), (2b, 3b, 1b), (2a, 3a, 1b), (2b, 3a, 1b), (2a, 3b, 1b);
(4c, 5c, 1a), (4e, 5e, 1a), (4c, 5e, 1f), (4e, 5c, 1f), (4e, 5e, 1f), (4c, 5c, 1f), (4e, 5c, 1a), (4c, 5e, 1a);
(6d, 7d,1a), (6f , 7f ,1a), (6d, 7f , 1c), (6f , 7d,1c), (6f , 7f ,1c), (6d, 7d, 1c), (6f , 7d, 1a), (6d, 7f , 1a).
The sets of strong colors for the respective composing 4-holes are:
(145, 167, 154, 176), (246, 257, 264, 275), (347, 356, 374, 365);
(213, 617, 312, 716), (246, 347, 624, 743), (257, 356, 752, 653);
(231, 451, 321, 541), (246, 356, 426, 536), (257, 347, 527, 437).
In fact, these 4-holes are respectively:
(2a, 3a, 2b, 3b), (3a, 1a, 3b, 1b), (2a, 1a, 2b, 1b);
(4c, 5e, 4e, 5c), (5c, 1a, 5e, 1f), (4c, 1a, 4e, 1f);
(7d, 6d, 7f ,6f), (7d, 1a, 7f ,1c), (6d, 1a, 6f , 1c).
4.2 Copies of K4 in G
There is one copy of K4 in G for each ordered Fano line xyz. Such a copy, denoted 〈xyz〉,
is formed by 3 pairs of equally weakly-colored opposite edges, with weak colors xa, yb and
zc. For each p ∈ F \ {x, y, z}, there is exactly one vertex (p, qara, qbrb, qcrc) of 〈xyz〉, with
x ∈ qara, y ∈ qbrb, z ∈ qcrc. The strong colors of the edges of 〈xyz〉 are precisely xyz. For
example, the triangles g(c1, a2, b2), g(c3, a0, b1), g(c2, a1, b0) and g(c0, a3, b2) from Subsection
3.1 are contained respectively in 〈347〉, 〈246〉, 〈257〉 and 〈356〉. Since there are 42 such copies
of K4 in G, we arrive at the following result.
Theorem 4.1 The graph G is a 12-regular {K4}
42{K2,2,2}
21-graph of order 42 and diameter
3. Each vertex of G is incident to exactly 3 copies of K2,2,2 and 4 copies of K4.
Proof: Let G′ be the graph defined by the same rules that define G on the unordered Fano
lines. Then it is not hard to prove that G′ is isomorphic to the graph 2K7, the complete
graph on 7 vertices with each edge doubled. The graph G is then a 6-fold covering graph
over G′. Also, the lexicographically smallest path realizing the diameter of G is the 3-path
(1a, 2a, 4a, 1d). The statement follows.
4.3 Disposition of copies of K2,2,2 and K4 in G
❝ ❝ ❝ ❝
4f7a 7e
6c 6c
1c 1c
6c 6c
5a 2b
5b 4a
Figure 2: Disposition of copies of K2,2,2 and K4 at vertex 7
f in G
Each point p of F determines a Pasch configuration PC(p), formed by the 4 lines of F that
do not contain p. This PC(p) may be denoted also pc(qara, qbrb, qcrc), where pqara, pqbrb, pqcrc
are the lines of F containing p. None of the lines of PC(p) contains either qara or qbrb or
qcrc. The 7 possible Pasch configurations here are:
PC(1) = pc(23, 45, 67) = {246, 257, 347, 356},
PC(2) = pc(13, 46, 57) = {145, 167, 347, 356},
PC(3) = pc(12, 47, 56) = {145, 167, 246, 257},
PC(4) = pc(15, 26, 37) = {123, 167, 257, 357},
PC(5) = pc(14, 27, 36) = {123, 167, 246, 347},
PC(6) = pc(17, 24, 35) = {123, 145, 257, 347},
PC(7) = pc(16, 25, 34) = {123, 145, 246, 356}.
Figure 2 shows the disposition of the induced copies of K2,2,2 and K4 incident to the vertex
7f in G, represented by 3 octahedra and 4 tetrahedra, respectively, with vertices and edges
accompanied by their respective simplified notations and weak colors. The 4 tetrahedra in
the figure are also shown as separate entities, for better distinction, while the 3 octahedra
are integrated in the central drawing as an upper-left, an upper-right and a lower-central oc-
tahedron, radiated from the central vertex, 7f . This 7 polyhedra can be blown up to 3-space
without more intersections than those of the vertices and edges shown in the figure. Starting
from the right upper corner in the figure and shown counterclockwise, the 3 octahedra have
respective composing 4-holes, each sub-indexed with its common weak color, as follows:
[347]
: (7f , 4e, 7e, 4f)3a , (7
f , 3d, 7e, 3e)4a , (3
d, 4e, 3e, 4f)7a ;
[257]
: (7f , 5a, 7a, 5f)2b , (7
f , 2b, 7a, 2d)5b , (2
b, 5a, 2d, 5f)7b ;
[167]
: (7f , 6d, 7d, 6f)1c , (7
f , 1a, 7d, 1c)6c , (1
a, 6d, 1c, 6f)7c .
The triangles in each octahedron here differ from those in the copies of K4 in G in the way
their edges are weakly colored. For example, the copies of K4 in Figure 2, namely those
denoted 〈321〉, 〈426〉, 〈356〉, 〈451〉, have their corresponding sets of constituent triangles
with the clockwise sequences of simplified notations and weak colors of respective alternate
incident vertices and edges, as follows:
{(7f , 2b, 5
f , 1c, 4
f , 3a), (6
f , 3a, 5
f , 1c, 4
f , 2b), (7
f , 1c, 6
f , 3a, 5
f , 2b), (7
f , 3a, 4
f , 2b, 6
f , 6c)};
{(7f , 6c, 1
c, 4a, 5
a, 2b), (3
e, 2b, 1
c, 4a, 5
a, 2b), (7
f , 4a, 3
e, 2b, 1
c, 4a), (7
f , 2b, 5
a, 6c, 3
e, 4a)};
{(7f , 3a, 4
e, 5b, 1
a, 6c), (2
b, 6c, 4
e, 5b, 1
a, 3a), (7
f , 6c, 1
a, 3a, 2
b, 5b), (7
f , 5b, 2
b, 6c, 4
e, 3a)};
{(2d, 1c, 3
d, 5b, 6
d, 4a), (7
f , 5b, 2
d, 1c, 3
d, 4a), (7
f , 6c, 6
d, 4a, 2
d, 5b), (7
f , 4a, 3
d, 5b, 6
d, 6c)}.
This reflects the fact that the vertex 7f = (7, 34, 25, 16) = (p, qa, ra, qbrb, qcrc) is associated
with the Pasch configuration pc(34, 25, 16) = pc(qara, qbrb, qcrc) given with its triples ordered
according to the presence of the different symbols 6= 7 at the 3 pair positions a, b, c, which
is shown in the ordered Fano lines 321 = qaqbqc, 426 = raqbrc, 356 = qarbrc, 451 = rarbqc,
or in their respectively associated tetrahedra: 〈321〉, 〈426〉, 〈356〉, 〈451〉. These ordered lines
form the ordered Pasch configuration pc(7f) = {321, 426, 356, 451}. Similarly, an ordered
Pasch configuration is associated to the set of copies of K4 incident to any other vertex of
G. Moreover, the following two results are readily checked.
Theorem 4.2 Any vertex v = (p, qara, qbrb, qcrc) of G can be expressed in such a way that
〈qaqbqc〉, 〈qarbrc〉, 〈raqbrc〉, 〈rarbqc〉 are its 4 incident copies of K4, reflecting their notation
and that of its 3 incident octahedra.
Proof: The ordered Pasch configuration pc(v) associated to v determines the ordered lines
qaqbqc, qarbrc, raqbrc, rarbqc associated to the copies of K4, while the 3 remaining triples of
F provide the data for the octahedra incident to v: [pqara]a, [pqbrb]b, [pqcrc]c.
Theorem 4.3 For any edge e of G, there exists exactly one copy of K2,2,2 and one of K4 in
G that intersect at e. Moreover, e is the only edge at which those copies intersect. Thus, G
is fastened.
Proof: Let e = vv′ have weak color qj , where v = (p, qara, qbrb, qcrc) and v
′ = (p′, q′ar
c). Then, the octahedron [pp
′p′′]j and the tetrahedron 〈xyz〉 are the copies of K2,2,2 and
K4 in the statement, where: (a) pp
′p′′ is the Fano line containing p and p′, (b) j ∈ {a, b, c} is
such that pp′′ = q′jr
j and pp
′ = qjrj and (c) xyz, one of the 4 ordered lines cited in Theorem
4.2 with respect to v, is the strong color of e.
For example, the edge 7f5a has weak color 2b and strong color 426. This is the only edge
shared by the octahedron [257]b and the tetrahedron 〈426〉.
5 Symmetric properties of G
Each automorphism τ ∈ A(G), is the composition of a permutation φτ of F with a per-
mutation ψτ of {a, b, c}. A set of 16 generators τi of A(G), (i = 1 . . . 16), is given by
τi = ψi ◦ φi = φi ◦ ψi, where we denote φi = φ
τi, ψi = ψ
τi, and
φ1 = (23)(67), φ2 = (45)(67), φ3 = (13)(57), φ4 = (46)(57),
φ5 = (12)(56), φ6 = (47)(56), φ7 = (15)(37), φ8 = (26)(37),
φ9 = (14)(27), φ10 = (27)(36), φ11 = (17)(35), φ12 = (24)(35),
φ13 = (16)(34), φ14 = (25)(34), ψ15 = (ac), ψ16 = (bc),
with ψi and φj taken as the identity maps of F and {a, b, c}, respectively, for 1 ≤ i ≤ 14
and j = 15, 16.
The subgroup Γ ⊂ A(G) that sends the lexicographically smallest arc (1a, 2a) onto it-
self, either directly or inversely oriented, includes exchanging, or not, its incident triangles
(2a, 3a, 1a) and (2a, 3b, 1a) in [123]a, or (1
a, 2a, 6f) and (1a, 2a, 5e) in 〈347〉. Thus, Γ contains
4 elements and has generating set {τ6 ◦ τ16, τ5}. Moreover, Γ is a subgroup of A([1]a), which
has generating set {τ1, τ2, τ5, τ6, τ16}. Furthermore, {τ1, τ2, τ5, τ6, τ15, τ16} is a generating set
for A(∪cj=a[123]j). The remaining automorphisms τi map A(∪
j=a[123]j) onto its nontrivial
cosets in A(G) by left multiplication. The subgroup of A(G) that fixes 1a has order 24 and
generating set {φ1, φ2, φ4 ◦φ16, φ6 ◦φ16, φ8 ◦φ15, φ10 ◦φ15, φ12 ◦φ15 ◦φ16, φ14 ◦φ15 ◦φ16}.
Theorem 5.1 G is a fastened {K4, K2,2,2}-ultrahomogeneous {K4}
42{K2,2,2}
21-graph which
is non-line-graphical, with
|A(G)| = 1008 = 4|E(G)|.
The edges of G can be seen as the left cosets of a subgroup Γ ⊂ A(G) of order 4, and its
vertices as the left cosets of a subgroup of A(G) of order 24.
Proof: Recall from Subsection 3.1 that |A(G)| = 1008.
Notice that A(〈347〉) = S4 is formed by 24 automorphisms. Since
|A(G)|
|A(〈347〉)|
= 1008
= 42,
then 〈347〉 is sent by an automorphism of G onto any other copy of K4 in G, from which it
is not difficult to see that G is K4-ultrahomogeneous.
Similarly, A([123]a) is formed by 48 automorphisms. Since
|A(G)|
|A([123]a)|
= 1008
= 21, then
[123]a is sent by an automorphism of G onto any other copy of K2,2,2 in G, from which it is
not difficult to see that G is K2,2,2-ultrahomogeneous.
On the other hand, |A(K2,2,2)| = 48 and |E(K2,2,2)| = 12 agree with the fact that
|Γ| =
|A(K2,2,2)|
|E(K2,2,2)|
= 4. Since G is the edge-disjoint union of 21 copies of K2,2,2, it contains a
total of 21|E(K2,2,2)| = 21×12 = 252 edges. Now, |A(G)| = 1008 = 21×48 = 21|A(K2,2,2)|.
This is 4 times the number 252 of edges of G. These edges correspond to the left cosets of
Γ in A(G) and its vertices to the left cosets of the stabilizer of 1a = (1, 23, 45, 67) in A(G),
whose order is 24.
6 Configurations associated with G
The symmetrical disposition of objects in G gives place to several combinatorial point-line
configurations and to their associated Levi, Menger, and dual Menger graphs.
We present the points and lines of 3 self-dual configurations obtained from G, and their
incidence relations:
1. the 42 vertices and 42 tetrahedra of G, and incidence given by inclusion of a vertex in
a tetrahedron; this is a self-dual (424)-configuration with 2-arc-transitive Levi graph
of diameter = girth = 6, automorphism-group order 2016, stabilizer order 24, distance
distribution vector (1, 4, 12, 24, 27, 14, 2) and isomorphic arc-transitive Menger graphs
of diameter = girth = 3, degree 12 and automorphism-group order 1008;
2. the 168 tetrahedral triangles and 168 octahedral triangles in G and their sharing of an
edge; this is a self-dual (1686)-configuration with semisymmetric Levi graph of diame-
ter = girth = 6, automorphism-group order 1008, common stabilizer order 6, distance
distribution vectors (1, 6, 24, 60, 111, 102, 32) and (1, 6, 24, 60, 108, 102, 35), (just differ-
ing at distances 4 and 6 by 3 vertices) and vertex-transitive Menger graphs of common
degree 24, diameter = girth = 3 and automorphism-group orders 1008 and 2016, re-
spectively.
3. the 168 tetrahedral triangles and 168 octahedral triangles in G and their sharing of an
edge; this is a self-dual (1686)-configuration with semisymmetric Levi graph of diame-
ter = girth = 6, automorphism-group order 1008, common stabilizer order 6, distance
distribution vectors (1, 6, 24, 60, 111, 102, 32) and (1, 6, 24, 60, 108, 102, 35), (just differ-
ing at distances 4 and 6 by 3 vertices) and vertex-transitive Menger graphs of common
degree 24, diameter = girth = 3 and automorphism-group orders 1008 and 2016, re-
spectively.
Another interesting configuration associated to G is formed by the 42 tetrahedra and 21
octahedra of G, and their sharing of an edge; this is a flag-transitive (426, 2112)-configuration.
Example. Let L be the Levi graph of the (424)-configuration in item 1 above. Then
((1, 23, 45, 67), 〈246〉, (3, 12, 47, 56), 〈145〉, (6, 17, 24, 35), 〈725〉, (1, 67, 23, 45))
and (〈123〉, (4, 15, 26, 37), 〈167〉, (2, 13, 46, 57), 〈347〉, (5, 36, 15, 27), 〈312〉)
are the lexicographically smallest paths realizing the diameter of L and departing from each
one of the two vertex parts of L. The second lexicographically smallest paths are
((1, 23, 45, 67), 〈246〉, (3, 12, 47, 56), 〈176〉, (4, 15, 37, 26), 〈572〉, (1, 45, 67, 23))
and (〈123〉, (4, 15, 26, 37), 〈167〉, (3, 12, 56, 47), 〈264〉, (5, 27, 36, 14), 〈231〉).
We reach this way to the only two vertices realizing the diameter of L starting from (1, 23,
45, 67), namely (1, 67, 23, 45) and (1, 45, 67, 23); respectively: starting from 〈123〉, namely
〈312〉 and 〈231〉. Those two pairs of paths reflect the correspondence between both parts of
L induced by the map Φ in Section 2.
7 On 6-holes and other subgraphs of G
1 2 3
5b6 4
✓✏ 5 2 7
1b6 4
✓✏ 7 2 5
3b6 4
✓✏ 3 2 1
7b6 4
❝6d 4c2a
6a 4a
6a 4a
4c 6d 4d
6a 4a
6a 4a
1 2 3
5c6 4
✓✏ 5 2 7
1c6 4
✓✏ 7 2 5
3c6 4
✓✏ 3 2 1
7c6 4
❝6c 4d2a
6a 4a
6a 4a
4d 6c 4c
6a 4a
6a 4a
Figure 3: Octahedral triangles of [246]a
Let us depict the Fano plane in an octahedral triangle, as shown for example in Figure 3
for the 8 triangles of [246]a, as follows. For each such triangle t, there is a unique i ∈ {a, b, c}
and a unique point p ∈ F such that the 3 vertices of t (looked upon as ordered pencils)
have p present in position i. The central point of the depiction of F inside each such t is
set to be p, subindexed by i. For example in Figure 3, this i appears as subindices c and b,
respectively, in the 4 top and 4 bottom triangles. Also, for each edge e of t with weak color
qj and strong color ℓ, the point in the depiction of F in t at the middle of e is set to be q,
and the ’external’ line of F containing q is set to be ℓ, with the points of ℓ \ {q} set near the
endvertices of e.
G contains 84 6-holes obtainable from the octahedral triangles of G based on these
depictions of F . This is exemplified on the left side of Figure 4, where the upper-left triangle
in Figure 3 appears as the bottom triangle, sharing its edge of weak color 2a with the central
6-hole. The 6-cycle of weak colors associated to this 6-hole is (2a3b1a2b3a1b).
1 2 3
5c6 4
❝ ❝ ❝
1 7 6
5c3 4
4 7 3
5c6 1
6 7 1
3 2 1
3 7 4
7b 7e
7a 7a
7b 7b
6a 4a
6b 4b
2465c
2463c
2465c
2465a
2461a
2467a
2467c
2463a
2461c
2467c
1235c 2465c
2465c
3475c 167
1675c 347
1a 3b 3a1b
7a 5a7f5f
3d 1f3f 1d
5c 7c5d7d
1e 3c1c 3e
7e 5e7b5b
Figure 4: A 6-hole and a star subgraph of G
Since the central color of each octahedral triangle having an edge in common with this
6-hole is 5c, and the line 123 has its points composing the weak colors of its edges, we denote
this 6-hole by 1235c , as indicated in the figure. Similar denominations are given to the 6-holes
neighboring this 1235c in the figure. We observe that the 6-holes neighboring 123
c on left and
right coincide with 2465c ; on upper-left and lower-right with 347
c; on lower-left and upper-
right with 1675c. These 4 6-holes form, together with the 8 octahedral triangles that appear
in their generation (i.e. the 6 in the figure plus (1b, 2a, 3a) and (1e, 2c, 3c)), a non-induced
toroidal subgraph of G that we may denote [5]c. In the same way, a non-induced subgraph
[w]d is obtained, for each w ∈ F and d ∈ {a, b, c}. The subgraph [[w]]d induced by [w]d in G
is formed by its union with the copies of K4 in G of the form 〈xaxbxc〉, with xd = w, a total
of 6 copies of K4 sharing each a 4-cycle with [w]d. Each [x1xbxc] here is the union of such a
4-cycle plus two additional edges of weak color wd. We get 21 subgraphs [[w]]d of G.
The 6-holes of the form xyzwd , where xyz is a fixed line of F , d varies in {a, b, c} and
w in F , are 12 in number and conform a subgraph [xyz] of G isomorphic to the star
Cayley graph ST4, that can be defined as the graph with vertex set S4 and each vertex
(a0, a1, a2, a3) ∈ S4 adjacent solely to (a1, a0, a2, a3), (a2, a1, a0, a3) and (a3, a1, a2, a0); see
[1, 4]. For example, the right side of Figure 4 depicts a (dotted) fundamental polygon of the
torus whose convex hull contains a representation of the subgraph [246] of G. This subgraphs
[xyz] are not induced in G. However, the graph [[xyz]] induced in G by each [xyz] is the
edge-disjoint union of [xyz] with the edge-disjoint union of six copies of K4 in G, namely:
〈xyz〉, 〈xzy〉, 〈yxz〉, 〈yzx〉, 〈zxy〉, 〈zyx〉. Figure 4 has 4 vertices painted black, which span a
copy of K4 in G but not in [246]. We get 7 subgraphs [xyz] of G.
Now, two new flag-transitive configurations associated to G (apart from those cited in
Section 6) are given by: (a) the 42 tetrahedra and 21 subgraphs [wd] in G, and inclusion
of a tetrahedron in a copy of T ; this is a (423, 216)-configuration; (b) the 21 subgraphs [wd]
and 7 copies of ST4 in G, and their sharing of a 6-hole; this is a (214, 712)-configuration.
When considered immersed in 3-space, the 21 octahedra and 28 toroidal subgraphs of
G presented above have faces that appear in canceling pairs, allowing the visualization of a
closed piecewise-linear 3-manifold. We ask: which are the properties of this manifold?
8 Open problems
It remains to see whether G is a Cayley graph or not. On the other hand, the definition of
G may be extended by means of projective planes, like the Fano plane, but over larger fields
than GF (2), starting with GF (3). Moreover, the two conditions of the definition of G in
Section 3 may be taken to 3 conditions, replacing F by a binary projective space P (r− 1, 2)
of dimension r−1, and the Fano lines by subspaces of dimension σ < r−1, where 2 < r ∈ ZZ
and σ ∈ (0, r−1)∩ZZ, and requiring, as a third condition, that the points of intersection of a
modified condition (b) form a projective hyperplane in P (r− 1, 2), (which was not required
for G, since it was a ready conclusion). The resulting graph, that appears in place of G,
may not be even connected, but the study of the component containing the lexicographically
smallest vertex could still be interesting. Another step would be taking the study over other
fields, starting with the ternary one.
Acknowledgement: The author is grateful to Josep Rifà and Jaume Pujol, for their friend-
ship and support, and to the referee, for his helpful observations, among which was suggesting
the hemi-rhombicuboctahedron as the open neighborhood of each vertex of G.
References
[1] S. B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnec-
tion networks, IEEE Trans. Comput., 38(1989) 555–565.
[2] N. Biggs, Algebraic Graph Theory, Cambridge University Press, 1993.
[3] H.S.M. Coxeter, Self-dual configurations and regular graphs, Bull. Amer. Math. Soc.,
56(1950) 413–455.
[4] I. J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs, Discrete Applied
Mathematics, 119 (2003) 319–328.
[5] J. Folkman, Regular line-symmetric graphs, J. Combin. Theory, 3(1967), 215–232.
[6] A. Gardiner, Homogeneous graphs, J. Combinatorial Theory (B), 20 (1976), 94-102.
[7] D. C. Isaksen, C. Jankowski and S. Proctor, On K∗-ultrahomogeneous graphs, Ars Com-
binatoria, Volume LXXXII, (2007), 83–96.
[8] C. Ronse, On homogeneous graphs, J. London Math. Soc. (2) 17 (1978), 375–379.
[9] J. Sheehan, Smoothly embeddable subgraphs, J. London Math. Soc. (2) 9 (1974), 212–218.
	Introduction
	Ordered Fano pencils
	The {K4,K2,2,2}-ultrahomogeneous graph G
	The automorphism group A(G) of G
	Copies of K2,2,2 and K4 in G
	Copies of K2,2,2 in G
	Copies of K4 in G
	Disposition of copies of K2,2,2 and K4 in G
	Symmetric properties of G
	Configurations associated with G
	On 6-holes and other subgraphs of G
	Open problems
