Tight factorizations of girth-$g$-regular graphs

Italo J. Dejter
University of Puerto Rico
Rio Piedras, PR 00936-8377
<EMAIL_ADDRESS>

###### Abstract

Girth-regular graphs with equal girth, regular degree and chromatic index are
studied for the determination of 1-factorizations with each 1-factor
intersecting every girth cycle. Applications to hamiltonian decomposability
and to 3-dimensional geometry are given. Applications are suggested for
priority assignment and optimization problems.

##  1 Introduction

Let $3\leq\kappa\in\mathbb{Z}$. Given a finite graph $\Gamma$ with girth
$g(\Gamma)=\kappa$, we inquire whether assigning $\kappa$ colors to the edges
of $\Gamma$ properly (i.e., no two adjacent edges of equal color in $\Gamma$)
can be performed so that each $\kappa$-cycle of $\Gamma$ has a bijection from
the edges of $\Gamma$ to the $\kappa$ colors. Such an inquiry is applicable to
managerial situations in which a number of agents must participate in
committees around round tables, with $\kappa$ stools about each table. A
roster of $\kappa$ tasks is handed to each agent at each round table, and such
an agent is assigned each of the $\kappa$ tasks but at pairwise different
tables. This can be interpreted as a 2-way (vertex incidence versus girth-
cycle membership) problem of sorting the $\kappa$ colors according to some
prioritization hierarchy. This way, an assignment problem is conceived, with
potential applications in optimization and decision making. We pass to
formalize such ideas.

Let $\Gamma$ be a finite connected $\kappa$-regular simple graph with
chromatic index $\chi^{\prime}(\Gamma)=\kappa$. Let $g=g(\Gamma)$ be the girth
of $\Gamma$. We say that $\Gamma$ is a $g$-tight graph if
$g=g(\Gamma)=\kappa=\chi^{\prime}(\Gamma)$. In each $g$-tight graph $\Gamma$,
it makes sense to look for a proper edge-coloring via $\kappa$ colors, each
girth cycle colored via a bijection between the cycle edges and the colors
they are assigned, precisely $\kappa$ colors. We will say that such a coloring
is an edge-girth coloring of $\Gamma$ and, in such a case, that $\Gamma$ is
edge-girth chromatic, or egc for short.

We focus on $g$-tight graphs that are girth-regular, a concept whose
definition in [17] we recall presently. Let $\\{e_{1},\ldots,e_{\kappa}\\}$ be
the set of edges incident to a vertex $v$. Let $(e_{i})$ be the number of
$\kappa$-cycles containing an edge $e_{i}$, for $1\leq i\leq\kappa$. Assume
$(e_{1})\geq(e_{2})\geq\ldots\geq(e_{\kappa})$. Let the signature of $v$ be
the $\kappa$-tuple $((e_{1}),(e_{2}),\ldots,(e_{\kappa}))$. A graph $\Gamma$
is said to be girth-regular if all its vertices have a common signature. In
such a case, the signature of any vertex of $\Gamma$ is said to be the
signature of $\Gamma$.

In this work, girth-regular graphs that are $g$-tight will be said to be
girth-$g$-regular graphs as well as $((e_{1}),(e_{2}),\ldots,(e_{g}))$-graphs,
or $(e_{1})(e_{2})\cdots(e_{g})$-graphs, if no confusion arises, where
$g=\kappa$. In this notation, a prefix

$a_{1}^{(1)}a_{1}^{(2)}\cdots a_{1}^{(m_{1})}a_{2}^{(1)}a_{2}^{(2)}\cdots
a_{2}^{(m_{2})}\cdots a_{t}^{(1)}a_{t}^{(2)}\cdots a_{t}^{(m_{t})}$

with $a_{i}^{(j)}=a_{i^{\prime}}^{(j^{\prime})}$ iff $i=i^{\prime}$ may be
abbreviated as $a_{1}^{m_{1}}a_{2}^{m_{2}}\cdots a_{t}^{m_{t}}$, where
superscripts equal to 1 may be omitted (e.g., $3221$ abbreviates to
$32^{2}1$). So, the prefixes $(e_{1})(e_{2})\cdots(e_{g})$ will include and
further be denoted as follows:

  1. (i)

$222=2^{3}$ and $110=1^{2}0$ in Section 2, (Theorems 1 and 4);

  2. (ii)

$3333=3^{4}$, $3322=3^{2}2^{2}$ and $2222=2^{4}$ in Section 3, (Theorem 10,
via Lemma 9);

  3. (iii)

$4443=4^{3}3$, $3221=32^{2}1$ and $3111=31^{3}$ in Section 4, (Theorem 21);

  4. (iv)

$1111=1^{4}$ in Section 5, (Theorems 24 and 27, via Lemma 9, or a variation of
it);

  5. (v)

$44400=4^{3}0^{2}$, $2^{3}0^{2}$, $8^{5}$ and $(12)^{5}$ in Section 6,
(Theorems 28, 29, 30 and 31).

Extending this context, girth-regular graphs $\Gamma$ of regular degree $g$
and girth larger than $g$ will be said to be $0^{g}$-graphs, or improper
$(e_{1})(e_{2})\cdots(e_{g})$-graphs.

Edge-girth colorings of $(e_{1})(e_{2})\ldots(e_{g})$-graphs are equivalent to
1-factorizations [22] such that the cardinality of the intersection of each
1-factor with each girth cycle is 1. These factorizations are said to be
tight, and the resulting colored girth cycles, tightly colored. Note a
$\Gamma$ with a tight factorization is egc. Unions of pairs of 1-factors of
such graphs are treated in Section 7 for their hamiltonian decomposability,
(Corollary 36). Applications to Möbius-strip compounds and hollow-triangle
polylinks are found in Section 8.

##  2 Egc girth-3-regular graphs

######  Theorem 1.

[17] There is only one $(e_{1})(e_{2})(e_{3})$-graph $\Gamma$ with
$(e_{1})(e_{2})(e_{3})=222=2^{3}$, namely $\Gamma=K_{4}$. Moreover,
$\Gamma=K_{4}$ is egc. All other proper $(e_{1})(e_{2})(e_{3})$-graphs are
$1^{2}0$-graphs, but not necessarily egc.

###### Proof.

For the first sentence in the statement, we refer to item (1) of Theorem 5.1
[17]. To see that $\Gamma=K_{4}$ is egc, we refer to Fig. 1(i), below. ∎

######  Remark 2.

In order to determine which $1^{2}0$-graphs are egc, let
$\Gamma^{\prime}=(V^{\prime},E^{\prime},\phi^{\prime})$ be a finite undirected
loopless cubic multigraph. Let $e\in E^{\prime}$ with
$\phi^{\prime}(e)=\\{u,v\\}$ and $u,v\in V^{\prime}$. Then, $e$ determines two
arcs (that is, ordered pairs of end-vertices of $e$) denoted $(e;u,v)$ and
$(e;v,u)$ (if the girth $g(\Gamma^{\prime})$ of $\Gamma^{\prime}$ is larger
than 2, then $\Gamma^{\prime}$ is a simple graph, a particular case of
multigraph). The following definition is an adaptation of a case of the
definition of generalized truncation in [10]. Let $A^{\prime}$ denote the set
of arcs of $\Gamma^{\prime}$. A vertex-neighborhood labeling of
$\Gamma^{\prime}$ is a function $\rho:A^{\prime}\rightarrow\\{1,2,3\\}$ such
that for each $u\in V^{\prime}$ the restriction of $\rho$ to the set
$A^{\prime}(u)=\\{(e;u,v)\in A^{\prime}:e\in
E^{\prime};\phi^{\prime}(e)=\\{u,v\\};v\in V^{\prime}\\}$ of arcs leaving $u$
is a bijection. For our purposes, we require $\rho(e;u,v)=\rho(e;v,u)$,
$\forall e\in E^{\prime}$ with $\phi^{\prime}(e)=\\{u,v\\}$, so that each
$e\in E^{\prime}$ is assigned a well-defined color from the color set
$\\{1,2,3\\}$. This yields a 1-factorization of $\Gamma^{\prime}$ with three
1-factors that we can call $E^{\prime}_{1},E^{\prime}_{2},E^{\prime}_{3}$ for
respective color 1, 2, 3, with $E^{\prime}$ being the disjoint union
$E^{\prime}_{1}\cup E^{\prime}_{2}\cup E^{\prime}_{3}$. For the sake of
examples in Fig. 1, to be presented below, let colors 1, 2 and 3 be taken as
red, blue and green, respectively.

Let $K_{3}$ be the triangle graph with vertex set $\\{v_{1},v_{2},v_{3}\\}$.
The triangle-replaced graph $\nabla(\Gamma^{\prime})$ of $\Gamma^{\prime}$
with respect to $\rho$ has vertex set $\\{(e_{i};u,v_{i}):u\in
V^{\prime};1\leq i\leq 3\\}$ and edge set

$\\{(e_{i};u,v_{i})(e_{j};u,v_{j})|v_{i}v_{j}\in E(K_{3}),u\in
V^{\prime}\\}\cup\\{u,v_{\rho(e;u,w)})(w,v_{\rho(e;w,u)})|e\in
E^{\prime};\phi(e)=\\{u,w\\}\\}.$

Note that $\nabla(\Gamma^{\prime})$ is a $1^{2}0$-graph. We will refer to the
edges of the form ($e_{i};u,v_{i})(e_{j};u,v_{j})$ as $\nabla$-edges or
triangle edges, and to the edges $(e_{i};u,v_{i})(e_{j};w,v_{j})$, $u\neq w$,
as $\Gamma^{\prime}$-edges or non-triangle edges. Observe that a
$\Gamma^{\prime}$-edge is incident only to $\nabla$-edges and that each vertex
of $\nabla(\Gamma^{\prime})$ is incident to precisely one
$\Gamma^{\prime}$-edge. This yields the following.

######  Observation 3.

[10] Let $\Gamma^{\prime}$ be a finite undirected cubic multigraph of girth
$g$. Then, for any vertex-neighborhood labeling $\rho$ of $\Gamma^{\prime}$,
the shortest cycle in the triangle-replaced graph $\nabla(\Gamma^{\prime})$
containing a $\Gamma^{\prime}$-edge is of length at least $2g$.

Figure 1: Producing $(e_{1})(e_{2})(e_{3})$-graphs that are egc.

We say that $\Gamma^{\prime}$ is a generalized snark if its chromatic index
$\chi^{\prime}(\Gamma^{\prime})$ is larger than 3. Two examples of generalized
snark are: (i) the Petersen graph and (ii) the multigraph obtained by joining
two $(2k+1)$-cycles ($k\geq 1$) via an extra-edge (a bridge between the two
$(2k+1)$-cycles) and adding $k$ parallel edges to each of the two
$(2k+1)$-cycles so that the resulting multigraph is cubic, see Fig. 1(r) for
$k=5$. The triangle-replaced graph
$\Gamma^{\prime}_{1}=\nabla(\Gamma^{\prime})$ of a generalized snark
$\Gamma^{\prime}$ will also be said to be a generalized snark. This
denomination will also be used for the triangle-replaced graphs
$\Gamma^{\prime}_{i+1}=\nabla(\Gamma^{\prime}_{i})$ of $\Gamma^{\prime}_{i}$,
for $i=1,2,\ldots$, etc. In addition, we will say that $\Gamma^{\prime}$ is
snarkless if it is not a generalized snark. Clearly, $K_{4}$ is snarkless.

Vertex-neighborhood labelings $\rho$ for the examples of $\Gamma^{\prime}$
below, represented in Fig. 1, have the elements 1, 2 and 3 of
$\rho(A^{\prime})$ interpreted respectively as edge colors red, blue and
green. Now, the smallest snarkless multigraphs $\Gamma^{\prime}\neq K_{4}$
are:

  1. (A)

the cubic multigraph $\Gamma^{\prime}_{A}$ of two vertices and three edges in
Fig. 1(g), with $\nabla(\Gamma^{\prime}_{A})$ being the triangular prism ${\rm
Prism}(K_{3})=K_{2}\square K_{3}$, in Fig. 1(h), where $V(K_{2})=\\{0,1\\}$
and $\square$ stands for the graph cartesian product [15];

  2. (B)

the cubic multigraph $\Gamma^{\prime}_{B}$ of four vertices resulting as the
edge-disjoint union of a 4-cycle and a 2-factor $2K_{2}$ in Fig. 1(a), with
$\nabla(\Gamma^{\prime}_{B})$ in Fig. 1(d).

Given a snarkless $\Gamma^{\prime}$, a new snarkless multigraph
$\Gamma^{\prime\prime}$ is obtained from $\Gamma^{\prime}$ by replacing any
edge $e$ with end-vertices say $u,v$, by the submultigraph resulting as the
union of a path $P_{4}=(u,u^{\prime},v^{\prime},v)$ and an extra edge with
end-vertices $u^{\prime},v^{\prime}$. For example, $\Gamma^{\prime}$ in Fig.
1(g) as $\Gamma^{\prime\prime}$ in Fig. 1(s) and
$\nabla(\Gamma^{\prime\prime})$ in Fig. 1(t). Using this replacement of an
edge $e$ by the said submultigraph, one can transform the submultigraph
$\Gamma^{\prime}_{B}$ with the enclosed blue edge $e$ in item (B), above, into
a $\Gamma^{\prime\prime}_{B}$ as in Fig. 1(b), with
$\nabla(\Gamma^{\prime\prime}_{B})$ in Fig. 1(e); or with the four red and
green edges into a $\Gamma^{\prime\prime}_{B}$ as in Fig. 1(c), with
$\nabla(\Gamma^{\prime\prime}_{B})$ in Fig. 1(f).

The triangle-replaced graph $\nabla(\Gamma^{\prime})$ of any snarkless
$(e_{1})(e_{2})(e_{3})$-graph $\Gamma^{\prime}$, either proper or improper,
with $(e_{1})(e_{2})(e_{3})\in\\{2^{3},1^{2}0,0^{3}\\}$, yields an egc
$1^{2}0$-graph, illustrated via the four graphs in Fig. 1(h–k), namely
$\Gamma^{\prime}=\nabla(\Gamma^{\prime}_{A}),K_{4},K_{3,3}$ and $Q_{3}$ (the
3-cube graph), onto the four $1^{2}0$-graphs $\Gamma$ in Fig. 1(m–p). This
raises the observation that non-equivalent 1-factorizations $F,F^{\prime}$ of
an $(e_{1})(e_{2})(e_{3})$-graph $\Gamma^{\prime}$, like in Fig. 1(k–l) for
$\Gamma^{\prime}=Q_{3}$, result in non-equivalent 1-factorizations
$\nabla(F),\nabla(F^{\prime})$ of $\Gamma=\nabla(\Gamma^{\prime})$,
represented in this case on $\Gamma=\nabla(\Gamma^{\prime})=\nabla(Q_{3})$ in
Fig. 1(p–q). This leads to the final assertion in Theorem 4, below.

Fig. 1(u) is the egc $1^{2}0$-graph given by $\nabla(\Gamma^{\prime})$ for the
dodecahedral graph ${\rm Dod}=\Gamma^{\prime}$, in which the union of any two
edge-disjoint 1-factors of a 1-factorization of $\Gamma^{\prime}$ yields a
Hamilton cycle. In contrast, the Coxeter graph ${\rm Cox}=\Gamma^{\prime}$ in
Fig. 1(v) is non-hamiltonian, but the union of any two of its (edge-disjoint)
1-factors is the disjoint union of two 14-cycles, whose apparent interiors are
shaded yellow and light gray in the figure. Thus,
$\Gamma=\nabla(\Gamma^{\prime})$ is an egc $1^{2}0$-graph.

######  Theorem 4.

A $1^{2}0$-graph $\Gamma$ is egc if and only if $\Gamma$ is the triangle-
replaced graph of a snarkless $\Gamma^{\prime}$. Moreover, non-equivalent
1-factorizations of such $\Gamma^{\prime}$ result in corresponding non-
equivalent 1-factorizations of $\Gamma$.

###### Proof.

There are two types of edges in a $1^{2}0$-graph $\Gamma$, namely the triangle
edges (those belonging to some triangle of $\Gamma$) and the remaining non-
triangle edges. Each vertex $v$ of $\Gamma$ is incident to a unique non-
triangle edge $e_{v}$ and is nonadjacent to a unique edge $\bar{e}_{v}$
(opposite to $v$) in the sole triangle $T_{v}$ of $\Gamma$ to which $v$
belongs. In any 1-factorization $F=(F_{1},\ldots,F_{g})$ of $\Gamma$, both
$e_{v}$ and $\bar{e}_{v}$ belong to the same factor $F_{i}$ ($i=1,\ldots,g$).
Moreover, each edge $e=\\{u,v\\}$ of $\Gamma$ (where $e=e_{u}=e_{v}$) belongs
solely to corresponding triangles $T_{u}$ and $T_{v}$ with opposite edges
$\bar{e}_{u}$ and $\bar{e}_{v}$. Clearly,
$\\{e=e_{u}=e_{v},\bar{e}_{u},\bar{e}_{v}\\}\subseteq F_{i}$ with equality
given precisely when $\Gamma$ is the triangular prism in Fig. 1(h).

We will define an inverse operator $\nabla^{-1}$ of $\nabla$ that applies to
each egc $1^{2}0$-graph $\Gamma$. Given one such $\Gamma$, contracting
simultaneously all the triangles $T$ of $\Gamma$ consists in removing the
edges of those $T$ and then identifying the vertices
$v_{1}^{T},v_{2}^{T},v_{3}^{T}$ of each $T$ into a corresponding single vertex
$v_{T}$, where $v_{i}^{T}$, for $i\in\\{1,2,3\\}$, has its unique incident
non-triangle edge of $\Gamma$ with color $i$. This is done so that whenever
two triangles $T$ and $T^{\prime}$ have respective vertices $v_{i}^{T}$ and
$v_{j}^{T^{\prime}}$ adjacent in $\Gamma$ ($i,j\in\\{1,2,3\\}$), then $i=j$
and the edge $v_{i}^{T}v_{i}^{T^{\prime}}$ of $\Gamma$ is removed and replaced
by a new edge $v_{T}v_{T^{\prime}}$. The result of these simultaneous triangle
contractions is a multigraph
$\Gamma^{\prime}=(V^{\prime},E^{\prime},\phi^{\prime})$ with each $v_{T}\in
V^{\prime}$ incident to three edges of $E^{\prime}$, one per each color in
$\\{1,2,3\\}$. The ensuing edge coloring in $\Gamma^{\prime}$ corresponds to a
vertex-neighborhood labeling $\rho:A^{\prime}\rightarrow\\{1,2,3\\}$ of
$\Gamma^{\prime}$, from which it follows that $\Gamma$ is the triangle-
replaced graph of $\Gamma^{\prime}$ with respect to $\rho$, that is:
$\nabla^{-1}(\Gamma)=\Gamma^{\prime}$. This establishes an identification of
$\Gamma$ and $\nabla(\Gamma^{\prime})$ so that the triangle-edges of $\Gamma$
are the $\nabla$-edges of $\nabla(\Gamma^{\prime})$, and the non-triangle
edges $\Gamma$ are the $\Gamma^{\prime}$-edges of $\nabla(\Gamma^{\prime})$.
This implies the main assertion of the statement of the theorem. ∎

##  3 Egc girth-4-regular graphs

######  Remark 5.

In this section and in Section 4, we consider
$(e_{1})(e_{2})(e_{3})(e_{4})$-graphs $\Gamma$ with
$(e_{1})(e_{2})(e_{3})(e_{4})\neq 1111$. Many such graphs are toroidal and
obtained from the square tessellation denoted by its Schläfli symbol
$\\{4,4\\}$. Let $T$ be the group of translations of the plane that preserve
such tessellation $\\{4,4\\}$. Then, $T$ is isomorphic to
$\mathbb{Z}\times\mathbb{Z}$ and acts transitively on the vertices of
$\\{4,4\\}$. If $U$ is a subgroup of finite index in $T$, then
${\mathcal{M}}=\\{4,4\\}/U$ is a finite map of type $\\{4,4\\}$ on the torus,
and every such map arises this way ([24], Section 6). A symmetry $\alpha$ of
$\\{4,4\\}$ acts as a symmetry of $\mathcal{M}$ if and only if $\alpha$
normalizes $U$. Every such $\mathcal{M}$ has symmetry group ${\rm
Aut}({\mathcal{M}})$ transitive on vertices, horizontal edges and vertical
edges. Moreover, for each edge $e$ of $\mathcal{M}$, there is a symmetry that
reverses $e$. Since this tessellation is a lattice, this yields a fundamental
region [4, 5] of such lattice. Such region will be called a cutout $\Phi$ and
be given by a rectangle $r$ squares wide and $t$ squares high, with the left
and right edges identified by parallel translation in order to get a toroidal
embedding of $\Gamma$, and the bottom edges identified with the top edges
after a shift of $s$ squares to the right, as in Fig. 6 of [24]. A toroidal
graph with such a cutout will be denoted $\\{4,4\\}_{r,t}^{s}$. While the aim
of [18, 19, 24] is the study of edge-transitive graphs, we find
1-factorizations of $g$-tight graphs in graphs $\\{4,4\\}_{r,t}^{s}$ of a more
ample nature. Our notation for the vertices of those cutouts will be $(i,j)$,
or $ij$ if no confusion arises, where $0\leq i<r$ and $0\leq j<t$, as in the
examples of tight factorizations in Fig. 2(d–j), with colors encoded by
numbers as follows: 1 for red, 2 for blue, 3 for green and 4 for hazel; in
case $t=1$ (Fig. 2(h–j)), we further simplify by writing $i$, instead of
$(i,0)$ or $i0$. (In Fig. 2, we take $a=10\in\mathbb{Z}$ and
$b=11\in\mathbb{Z}$).

######  Remark 6.

If a fundamental region $\Phi$ of $\\{4,4\\}$ as in Remark 5 is identified in
reverse on a pair $\mathcal{P}$ of opposite sides, and directly on the other
pair, we get a Klein bottle $\mathcal{K}$ [23]. There are egc-graphs that are
skeletons of a $\\{4,4\\}$-tessellation of $\mathcal{K}$, for example in Fig.
2(b), whose embedding into $\mathcal{K}$ has corresponding cutout that can be
obtained from the one of $\\{4,4\\}_{r,t}^{s}$ above (with $(r,t,s)=(6,3,0)$)
first by replacing the vertical edges by corresponding square-face diagonals,
while keeping the horizontal edges (so the new faces are lozenge rhombi), and
second by identifying the horizontal top and bottom borders of the original
cutouts, as well as the left and right borders, these with reverse
orientations, with the resulting $\mathcal{K}$-embedding that we will denote
$\lfloor 4,4\rceil_{r,t}^{s}$. Then, the example of Fig. 2(b) is in $\lfloor
4,4\rceil_{6,3}^{0}$. If $\Phi$ is identified in reverse on both pairs of
opposite sides, a projective-planar graph is obtained. This can be ruled out
because $\\{4,4\\}$-tessellations only exist on surfaces with Euler
characteristic 0.

Figure 2: Examples of $(e_{1})(e_{2})(e_{3})(e_{4})$-graphs.

######  Remark 7.

Let $0<n\in\mathbb{Z}$. The $n$-cube graph $Q_{n}$ has as vertices the
$n$-tuples with entries in $\mathbb{Z}_{2}$ and edges only between vertices at
unit Hamming distance. In Subsection 3.1, we consider the 4-cube graph
$Q_{4}=\\{4,4\\}_{4,4}^{0}$. Other $(e_{1})(e_{2})(e_{3})(e_{4})$-graphs with
$(e_{1})(e_{2})(e_{3})(e_{4})\neq 1111$ and that are not prisms of
$(e_{1})(e_{2})(e_{3})$-graphs are:

  1. (i)

the bipartite complement of the Heawood graph, in Subsection 3.3;

  2. (ii)

the subdivided double $\mathbb{D}\Gamma$ [18, 24] of a $4$-regular graph
$\Gamma$ is the bipartite graph with vertex set
$(V(\Gamma)\times\mathbb{Z}^{2})\cup E(\Gamma)$ and an edge between vertices
$(v,i)\in V(\Gamma)\times\mathbb{Z}^{2}$ and $e\in E(\Gamma)$ whenever $v$ is
incident to $e$ in $\Gamma$; [18, Lemma 4.2] asserts that if $\Gamma$ is
4-regular and arc-transitive, then $\mathbb{D}\Gamma$ is 4-regular and
semisymmetric; for example, the Folkman graph (Fig. 2(a)) is the subdivided
double $\mathbb{D}K_{5}$ of the complete graph $K_{5}$;

  3. (iii)

the circulant graphs, i.e. the Cayley graphs $C_{n}(i,j)$ of the cyclic group
$\mathbb{Z}_{n}$ ($n>6$) with generating sets $\\{\pm i,\pm j\\}$, where
$1\leq i<j<\frac{n}{2}$, and $\gcd(n,i,j)=1$; most of these are $2^{4}$-graphs
(assuming $n$ even, otherwise chromatic index is not 4), with additional
cycles appearing whenever a congruence $\lambda i\pm(4-\lambda)j\equiv
0\pmod{n}$ holds, (e.g., $C_{14}(2,3)$ is a $2^{4}$-graph, $C_{12}(2,3)$ is a
$3^{2}2^{2}$-graph, $C_{10}(1,3)$ is a $6^{4}$-graph and $C_{8}(1,3)\equiv
K_{4,4}$ is a $9^{4}$-graph); however, such graphs $C_{n}(i,j)$ can always be
seen as toroidal graphs;

  4. (iv)

the wreath graphs $W(n,2)=C_{n}[\overline{K_{2}}]$ ($n>4$), i.e. lexicographic
products of an $n$-cycle and the complement $\overline{K_{2}}$ of $K_{2}$;
these are $5^{4}$-graphs; ($W(4,2)\equiv K_{4,4}$ is a $9^{4}$-graph).

######  Remark 8.

If an $(e_{1})(e_{2})(e_{3})(e_{4})$-graph $\Gamma$ as in Remark 7 contains a
subgraph $\Gamma^{\prime}$ guaranteeing that $\Gamma$ is not an egc-graph,
then $\Gamma^{\prime}$ is said to be an egc-obstruction. A subgraph
$\Gamma^{\prime}\equiv K_{2,3}$ is an egc-obstruction for a girth-4-regular
graph $\Gamma$, since each of the proper edge-colorings of $\Gamma$ contains a
quadrangle of $\Gamma^{\prime}$ with only two colors. In Fig. 2(a), one such
graph $\Gamma$, namely $\Gamma=\mathbb{D}K_{5}$ is presented with a subgraph
$\Gamma^{\prime}\equiv K_{2,3}$ formed by a green quadrangle and a red 2-path.
$C_{10}(1,3)$ and $W(6,2)$ also have obstruction isomorphic to $K_{2,3}$.

The following lemma is a tool for Theorems 9 and 27, and a variation of it,
for Theorem 24.

######  Lemma 9.

A sufficient condition for an $(e_{1})(e_{2})(e_{3})(e_{4})$-graph $\Gamma$
with $(e_{i})<3$ ($i=1,2,3,4$) to be egc is existence of 2-factorization
$\\{F_{1},F_{2}\\}$ of $\Gamma$ such that each 2-factor $F_{i}$ ($i=1,2$):

  1. 1.

is the disjoint union of even-length cycles; and

  2. 2.

has an even-length cycle $D(C)$ as in item 1, for each 4-cycle $C$ of
$\Gamma$, sharing with $C$ exactly two consecutive edges.

###### Proof.

A 1-factorization of $F_{1}$ via colors 1 and 2 and a 1-factorization of
$F_{2}$ via colors 3 and 4 exist and form a tight 1-factorization of $\Gamma$.
∎

######  Theorem 10.

The following $3^{4}$-, $3^{2}2^{2}$\- and $2^{4}$-graphs exist, and are egc
or not, as indicated:

  1. 1.

$3^{4}$-graphs comprising the:

    1. (a)

bipartite complement of the Heawood graph, which is not egc, (Subsection 3.3);

    2. (b)

4-regular subdivided doubles $\mathbb{D}\Gamma$ of $4$-regular graphs
$\Gamma$, which are not egc;

    3. (c)

4-cube graph $Q_{4}=\\{4,4\\}_{4,4}^{0}$, which is egc in two different,
orthogonally related ways, (Subsections 3.1-3.2, Remark 11; an initial example
is in Fig. 2(d));

  2. 2.

$2^{2}3^{2}$-graphs (assuming $0<t\leq r$ and $0\leq s<r$), comprising:

    1. (a)

$\\{4,4\\}_{2\ell,4}^{0}$: egc $\Leftrightarrow\ell\in(3,\infty)\cap
2\mathbb{Z}$; (concatenating copies of $\\{4,4\\}_{4,4}^{0}$, in Fig. 2(d));

    2. (b)

$\\{4,4\\}_{4s,1}^{s}$: egc $\Leftrightarrow
s\in(4,\infty)\cap\mathbb{Z}\setminus 2\mathbb{Z}$; (Fig. 2(h–i), for
$r_{t}^{s}=20_{1}^{5},28_{1}^{7}$);

  3. 3.

$2^{4}$-graphs (assuming $0<t\leq r$ and $0\leq s<r$) comprising:

    1. (a)

$\\{4,4\\}_{r,1}^{s}$: egc $\Leftrightarrow r\in 2\mathbb{Z}\setminus
4\mathbb{Z}$, $s\in\mathbb{Z}\setminus(2\mathbb{Z}\cup 1)$ and $r\neq 3s+1$;
(Fig. 2(j), $r_{t}^{s}=22_{1}^{5}$);

    2. (b)

$\\{4,4\\}_{r,2}^{s}$: egc $\Leftrightarrow r\in[10,\infty)\cap 2\mathbb{Z}$
and $s\in[4,r-4]\cap 2\mathbb{Z}$; (Fig. 2(e–f),
$\\!r_{t}^{s}=\\!12_{2}^{4},10_{2}^{4}$);

    3. (c)

$\\{4,4\\}_{r,3}^{s}$: egc $\Leftrightarrow r\in[6,\infty)\cap 2\mathbb{Z}$
and $s=[3,r-3]\\!\setminus\\!2\mathbb{Z}$; (Fig. 2(g), $r_{t}^{s}=6_{3}^{3}$);

    4. (d)

$\\{4,4\\}_{r,4}^{s}$: egc $\Leftrightarrow 4\leq r\in 2\mathbb{Z}$ and
$0<s\in 2\mathbb{Z}$; (color pattern as in Fig. 2(e–g),(j);

    5. (e)

$\\{4,4\\}_{r,t}^{s}$, $t\in[4,\infty)$: egc $\Leftrightarrow r\in
2\mathbb{Z}$ and $t+s\in 2\mathbb{Z}$; (color pattern as in Fig. 2(c));

    6. (f)

$\lfloor 4,4\rceil_{r,t}^{0}$: egc $\Leftrightarrow r\in[6,\infty)\cap
2\mathbb{Z}$ and $t\in[3,\infty)\cap\mathbb{Z}\setminus 2\mathbb{Z}$; (Fig.
2(b), $r_{t}^{s}=6_{3}^{0},8_{3}^{0}$).

A cycle of a graph $\Gamma$ as in Remarks 5-6 is said to be 1-zigzagging if it
is formed by alternate horizontal and non-horizontal (i.e., all vertical or
all $45^{\circ}$-tilted) edges. A 2-factor of $\Gamma$ is said to be
1-zigzagging if its composing cycles are 1-zigzagging. A 2-factorization of
$\Gamma$ is said to be 1-zigzagging if its composing 2-factors are
1-zigzagging.

###### Proof.

We pass to analyze the different items composing the statement of Theorem 10.

Items 1 and 2: Item 1($a$) is proved in Subsection 3.3. The graphs of item
1($b$) have egc-obstructions (see Remark 8) formed by three edge-disjoint
paths of length 2 between two nonadjacent vertices, e.g., $\mathbb{D}K_{5}$ in
Fig. 2(a), with egc-obstruction formed by four green edges and two red edges.
Items 1($c$) and 2($b$) are proved in Subsection 3.2, Remark 11; (see also
Fig. 2(d)). Item 2($a$) is proved by concatenating copies of
$\\{4,4\\}_{4,4}^{0}$, as in Fig. 2(d).

Item 3: Lemma 9 applies to each $\Gamma$ as in Remarks 5-6 via the
1-zigzagging 2-factorization $(12)(34)$, which contains its 2-factors having
exactly two consecutive edges in common with each 4-cycle, as shown in Fig.
2(e,f,g,j,b,c). In items 3($a$–$f$), the non-egc cases indicated via
“$\Leftrightarrow$” include those not satisfying the sufficient condition of
Lemma 9, because such condition becomes also necessary for each $\Gamma$
arising from a toroidal or Klein-bottle cutout as in Remarks 5– 6. Moreover,
all the 1-zigzagging cycles in $\Gamma$ have even length and share two
consecutive edges with each 4-cycle precisely where indicated via
“$\Leftrightarrow$” in items 3($a$–$f$). Furthermore, in Fig. 2(e,f,g,j), the
thin diagonals separate those pairs of consecutive edges (for the
2-factorization $(12)(34)$), while the dashed ones do the same for the
2-factorization $(14)(23)$. In addition, note the exclusion in item 3($a$) of
the cases $\\{4,4\\}_{6,1}^{1}$ and those for which $r=3s+1$, and in item
3($c$) the case $\\{4,4\\}_{6,3}^{1}$. In item 3($b$), note the lower bound
for $r$, due to $\\{4,4\\}_{8,2}^{4}$ being a $3^{2}2^{2}$-graph but not egc.
For item 3($e$), the case $s=0$ is covered in item 2($a$).

For the cases of Klein-bottle graphs in item 3($f$), there are two different
color patterns, the first one, exemplified in Fig. 2(b), valid for $6\leq r\in
2\mathbb{Z}$ and the second one further restricted to having $r\in
4\mathbb{Z}$, with more than two colors on each horizontal line. Note the
exclusion of the cases $\lfloor 4,4\rceil_{4,t}^{0}$
($3<t\in\mathbb{Z}\setminus 2\mathbb{Z}$), for they are not girth-regular. ∎

The egc-cases of Theorem 10 item 3 are exemplified respectively in Fig.
2(e,f,g,j,b,c), characterized by having cycles with blue-hazel horizontal
edges and cycles with red-green non-horizontal edges. However, transposing the
two colors in 1-zigzagging cycles of 2-factors in 2-factorizations $(12)(34)$,
$(13)(24)$ or $(14)(23)$ yield tight factorizations with horizontal cycles
colored with more than 2 colors.

###  3.1 The 4-cube as a twice-egc girth-4-regular graph

Consider the three mutually orthogonal Latin squares of order 4, or MOLS(4)
[3] contained as the second, third and fourth rows in the following compound
matrix:

$\displaystyle\begin{array}[]{c|cccc}&1&2&4&7\\\ \hline\cr
0&111&222&333&444\\\ 3&243&134&421&312\\\ 5&324&413&142&231\\\
6&432&341&214&123\end{array}$ (6)

where for us row and column headings will stand for the following 4-tuples:

$\displaystyle\begin{array}[]{cccccccc}0\\!=\\!0000,\\!&\\!1\\!=\\!1000,\\!&\\!2\\!=\\!0100,\\!&\\!3\\!=\\!1100,\\!&\\!4\\!=\\!0010,\\!&\\!5\\!=\\!1010,\\!&\\!6\\!=\\!0110,\\!&\\!7\\!=\\!1110,\\\
0^{\prime}\\!=\\!0001,\\!&\\!1^{\prime}\\!=\\!1001,\\!&\\!2^{\prime}\\!=\\!0101,\\!&\\!3^{\prime}\\!=\\!1101,\\!&\\!4^{\prime}\\!=\\!0011,\\!&\\!5^{\prime}\\!=\\!1011,\\!&\\!6^{\prime}\\!=\\!0111,\\!&\\!7^{\prime}\\!=\\!1111.\end{array}$
(9)

Figure 3: Factors of $K_{4,4}$ and toroidal cutouts of $Q_{4}$ with 0-, 1- and
2-color 4-cycles.

Based on display (6), the top of Fig. 3 contains three copies of $K_{4,4}$
properly colored in a mutually-orthogonal way, where colors are numbered as
established in Remark 5. Letting $\phi:Q_{4}\rightarrow K_{4,4}$ be the
canonical projection map of $Q_{4}$ seen as a double covering of $K_{4,4}$
obtained by identifying the pairs of antipodal vertices of
$Q_{4}=\\{4,4\\}_{4,4}^{0}$, these vertices denoted as in display (9), note
that in the bottom of Fig. 3 corresponding copies of the colored inverse
images $\phi^{-1}(K_{4,4})$ of the three mentioned copies of $K_{4,4}$ are
depicted. The leftmost copy of $Q_{4}$ in Fig. 3 has color $i$ attributed
precisely to those edges parallel to the $i^{th}$ coordinate direction, for
$i=1,2,3,4$. This constitutes a 1-factorization
$F_{0}=\\{F_{0}^{1},F_{0}^{2},F_{0}^{3},F_{0}^{4}\\}$ of $Q_{4}$. On the other
hand, the center and rightmost copies of $Q_{4}$ in the figure determine
1-factorizations $F_{1}$ and $F_{2}$ of $Q_{4}$ for which each girth cycle of
$Q_{4}$ intersects every composing 1-factor $F_{i}^{j}$ of $F_{i}$, where
$i=1,2$ and $j=$ 1 (red), 2 (blue), 3 (green), 4 (hazel).

For each edge $e$ of $Q_{4}$, we say that $e$ has $i$-color
$j\in\\{1,2,3,4\\}$ if $e\in F_{i}^{j}$. Then, each 4-cycle of $Q_{4}$ has
opposite edges with a common 0-color in $\\{1,2,3,4\\}$, with a total of two
(nonadjacent) 0-colors in $\\{1,2,3,4\\}$ per 4-cycle, say 0-colors
$\ell_{1},\ell_{2}\in\\{1,2,3,4\\}$, with $\ell_{1}\neq\ell_{2}$, so one such
4-cycle can be expressed as $(\ell_{1},\ell_{2},\ell_{1},\ell_{2})$. On the
other hand, the 4-cycles of $Q_{4}$ use all four $i$-colors 1,2,3,4, once
each, for $i=1,2$.

There are twenty-four 4-cycles in $Q_{4}$, six of each of the 0-color 4-cycles
expressed in the first two columns of the following array, with two
complementary 0-color 4-cycles per row. On the other hand, the third and
fourth columns here contain respectively the 1-color and 2-color 4-cycles
corresponding to the 0-color 4-cycles in the first two columns:

$\displaystyle\begin{array}[]{||c|c||c||c||}\hline\cr(1212)&(3434)&(1234)&(1243)\\\
(1313)&(2424)&(1324)&(1342)\\\ (1414)&(2323)&(1423)&(1432)\\\
\hline\cr\end{array}$ (13)

###  3.2 Toroidal representation tables

######  Remark 11.

The triple array in Table 1 presents $F_{i}$ ($i=0,1,2$) in schematic
representations of $Q_{4}=\\{4,4\\}_{4,4}^{0}$, where $\circ$ stands for a
vertex of $Q_{4}$ and $\square$ stands for an $i$-color 4-cycle. This table
guarantees Theorem 10 item 3($c$) via the last two columns of color quadruples
in display (13), because the four colors are employed on the edges of each
4-cycle:

$\begin{array}[]{||ccccccccc||ccccccccc||ccccccccc||}\hline\cr\hline\cr\circ&3\\!&\circ&2\\!&\circ&3\\!&\circ&2\\!&\circ&\circ&1\\!&\circ&3\\!&\circ&2\\!&\circ&4\\!&\circ&\circ&2\\!&\circ&1\\!&\circ&4\\!&\circ&3\\!&\circ\\\
4\\!&\square\\!&4\\!&\square\\!&4\\!&\square\\!&4\\!&\square\\!&4\\!&2\\!&\square\\!&4\\!&\square\\!&1\\!&\square\\!&3\\!&\square\\!&2\\!&1\\!&\square\\!&4\\!&\square\\!&3\\!&\square\\!&2\\!&\square\\!&1\\\
\circ&3\\!&\circ&2\\!&\circ&3\\!&\circ&2\\!&\circ&\circ&3\\!&\circ&2\\!&\circ&4\\!&\circ&1\\!&\circ&\circ&3\\!&\circ&2\\!&\circ&1\\!&\circ&4\\!&\circ\\\
1\\!&\square\\!&1\\!&\square\\!&1\\!&\square\\!&1\\!&\square\\!&1\\!&4\\!&\square\\!&1\\!&\square\\!&3\\!&\square\\!&2\\!&\square\\!&4\\!&2\\!&\square\\!&1\\!&\square\\!&4\\!&\square\\!&3\\!&\square\\!&2\\\
\circ&3\\!&\circ&2\\!&\circ&3\\!&\circ&2\\!&\circ&\circ&2\\!&\circ&4\\!&\circ&1\\!&\circ&3\\!&\circ&\circ&4\\!&\circ&3\\!&\circ&2\\!&\circ&1\\!&\circ\\\
4\\!&\square\\!&1\\!&\square\\!&4\\!&\square\\!&1\\!&\square\\!&4\\!&1\\!&\square\\!&3\\!&\square\\!&2\\!&\square\\!&4\\!&\square\\!&1\\!&3\\!&\square\\!&2\\!&\square\\!&1\\!&\square\\!&4\\!&\square\\!&3\\\
\circ\\!&3\\!&\circ&2\\!&\circ&3\\!&\circ&2\\!&\circ&\circ&4\\!&\circ&1\\!&\circ&3\\!&\circ&2\\!&\circ&\circ&1\\!&\circ&4\\!&\circ&3\\!&\circ&2\\!&\circ\\\
1\\!&\square\\!&1\\!&\square\\!&1\\!&\square\\!&1\\!&\square\\!&1\\!&3\\!&\square\\!&2\\!&\square\\!&4\\!&\square\\!&1\\!&\square\\!&3\\!&4\\!&\square\\!&3\\!&\square\\!&2\\!&\square\\!&1\\!&\square\\!&4\\\
\circ\\!&3\\!&\circ&2\\!&\circ&3\\!&\circ&2\\!&\circ&\circ&1\\!&\circ&3\\!&\circ&2\\!&\circ&4\\!&\circ&\circ&2\\!&\circ&1\\!&\circ&4\\!&\circ&3\\!&\circ\\\
\hline\cr\hline\cr\end{array}$ Table 1: Representations of $F_{i}$
($i=0,1,2$).

  1. (a)

either as horizontal or vertical color quadruples (as in display 13)
alternated with the symbols $\circ$ that represent the vertices of $Q_{4}$;

  2. (b)

or as quadruples around the symbols $\square$ representing the other 4-cycles.

$\begin{array}[]{||ccccccccccc||ccccccccccccccc||}\hline\cr\hline\cr_{00}\\!\\!&2\\!\\!&{}_{01}\\!\\!&4\\!\\!&{}_{02}\\!\\!&1\\!\\!&{}_{03}\\!\\!&3\\!\\!&{}_{04}\\!\\!&2\\!\\!&{}_{05}&{}_{00}\\!\\!&2\\!\\!&{}_{01}\\!\\!&1\\!\\!&{}_{02}\\!\\!&3\\!\\!&{}_{03}\\!\\!&4\\!\\!&{}_{04}\\!\\!&2\\!\\!&{}_{05}\\!\\!&1\\!\\!&{}_{06}\\!\\!&3\\!\\!&{}_{07}\\\
1\\!\\!&\square\\!\\!&3\\!\\!&\square\\!\\!&2\\!\\!&\square\\!\\!&4\\!\\!&\square\\!\\!&1\\!\\!&\square\\!\\!&3&1\\!\\!&\square\\!\\!&3\\!\\!&\square\\!\\!&4\\!\\!&\square\\!\\!&2\\!\\!&\square\\!\\!&1\\!\\!&\square\\!\\!&3\\!\\!&\square\\!\\!&4\\!\\!&\square\\!\\!&2\\\
_{05}\\!\\!&4\\!\\!&{}_{06}\\!\\!&1\\!\\!&{}_{07}\\!\\!&3\\!\\!&{}_{08}\\!\\!&2\\!\\!&{}_{09}\\!\\!&4\\!\\!&{}_{10}&{}_{07}\\!\\!&4\\!\\!&{}_{08}\\!\\!&2\\!\\!&{}_{09}\\!\\!&1\\!\\!&{}_{10}\\!\\!&3\\!\\!&{}_{11}\\!\\!&4\\!\\!&{}_{12}\\!\\!&2\\!\\!&{}_{13}\\!\\!&1\\!\\!&{}_{14}\\\
3\\!\\!&\square\\!\\!&2\\!\\!&\square\\!\\!&4\\!\\!&\square\\!\\!&1\\!\\!&\square\\!\\!&3\\!\\!&\square\\!\\!&2&2\\!\\!&\square\\!\\!&1\\!\\!&\square\\!\\!&3\\!\\!&\square\\!\\!&4\\!\\!&\square\\!\\!&2\\!\\!&\square\\!\\!&1\\!\\!&\square\\!\\!&3\\!\\!&\square\\!\\!&4\\\
_{10}\\!\\!&1\\!\\!&{}_{11}\\!\\!&3\\!\\!&{}_{12}\\!\\!&2\\!\\!&{}_{13}\\!\\!&4\\!\\!&{}_{14}\\!\\!&1\\!\\!&{}_{15}&{}_{14}\\!\\!&3\\!\\!&{}_{15}\\!\\!&4\\!\\!&{}_{16}\\!\\!&2\\!\\!&{}_{17}\\!\\!&1\\!\\!&{}_{18}\\!\\!&3\\!\\!&{}_{19}\\!\\!&4\\!\\!&{}_{20}\\!\\!&2\\!\\!&{}_{21}\\\
2\\!\\!&\square\\!\\!&4\\!\\!&\square\\!\\!&1\\!\\!&\square\\!\\!&3\\!\\!&\square\\!\\!&2\\!\\!&\square\\!\\!&4&4\\!\\!&\square\\!\\!&2\\!\\!&\square\\!\\!&1\\!\\!&\square\\!\\!&3\\!\\!&\square\\!\\!&4\\!\\!&\square\\!\\!&2\\!\\!&\square\\!\\!&1\\!\\!&\square\\!\\!&3\\\
_{15}\\!\\!&3\\!\\!&{}_{16}\\!\\!&2\\!\\!&{}_{17}\\!\\!&4\\!\\!&{}_{18}\\!\\!&1\\!\\!&{}_{19}\\!\\!&3\\!\\!&{}_{00}&{}_{21}\\!\\!&1\\!\\!&{}_{22}\\!\\!&3\\!\\!&{}_{23}\\!\\!&4\\!\\!&{}_{24}\\!\\!&2\\!\\!&{}_{25}\\!\\!&1\\!\\!&{}_{26}\\!\\!&3\\!\\!&{}_{27}\\!\\!&4\\!\\!&{}_{00}\\\
4\\!\\!&\square\\!\\!&1\\!\\!&\square\\!\\!&2\\!\\!&\square\\!\\!&3\\!\\!&\square\\!\\!&4\\!\\!&\square\\!\\!&1&3\\!\\!&\square\\!\\!&4\\!\\!&\square\\!\\!&2\\!\\!&\square\\!\\!&1\\!\\!&\square\\!\\!&3\\!\\!&\square\\!\\!&4\\!\\!&\square\\!\\!&2\\!\\!&\square\\!\\!&1\\\
_{00}\\!\\!&2\\!\\!&{}_{01}\\!\\!&4\\!\\!&{}_{02}\\!\\!&1\\!\\!&{}_{03}\\!\\!&3\\!\\!&{}_{04}\\!\\!&2\\!\\!&{}_{05}&{}_{00}\\!\\!&2\\!\\!&{}_{01}\\!\\!&1\\!\\!&{}_{02}\\!\\!&3\\!\\!&{}_{03}\\!\\!&4\\!\\!&{}_{04}\\!\\!&2\\!\\!&{}_{05}\\!\\!&1\\!\\!&{}_{06}\\!\\!&3\\!\\!&{}_{07}\\\
\hline\cr\hline\cr\end{array}$ Table 2: Distinction of the two cases $F_{1}$
and $F_{2}$.

By associating the oriented quadruple (1,3,2,4) (resp. (3,4,1,2)) of
successive edge colors on the left-to-right and the downward (resp. the right-
to-left and the downward) straight paths in $F_{1}$ (resp. $F_{2}$),
situations that we indicate by “$\searrow(1,3,2,4)$” (resp.
“$\swarrow(3,4,1,2)$”), a complete invariant for $F_{1}$ (resp. $F_{2}$) is
obtained that we denote by combining between square brackets the just
presented notations:

$[a_{\swarrow 12,34},b_{\searrow 13,24},\searrow(1,3,2,4)],\mbox{ (resp.
}[a_{\searrow 13,24},b_{\swarrow 12,34},\swarrow(3,4,1,2)]).$

This invariant distinguishes $F_{1}$ and $F_{2}$ from each other and is
generalized for the toroidal graphs in Theorem 10, as we will see below in
this subsection.

Table 1 is also presented to establish similar patterns, like in Table 2,
allowing in a likewise manner to guarantee Theorem 10 item 2($b$). We say that

  1. 1.

$F_{1}$ has $a_{\swarrow 12,34}$-zigzags if any 1-zigzagging path obtained by
walking left, down, left, down and so on, alternates either colors 1 and 2, or
colors 3 and 4;

  2. 2.

$F_{1}$ has $b_{\searrow 13,24}$-zigzags if any 2-zigzagging path obtained by
walking right, right, down, down and so on, alternates either colors 1 and 3,
or colors 2 and 4;

  3. 3.

$F_{2}$ has $a_{\searrow 13,24}$-zigzags if any 2-zigzagging path obtained by
walking left, left, down, down and so on, either alternates colors 1 and 2, or
colors 3 and 4;

  4. 4.

$F_{2}$ has $b_{\swarrow 12,34}$-zigzags if any 1-zigzagging path obtained by
walking right, down, right, down and so on, either alternates colors 1 and 3,
or colors 2 and 4.

A representation as in Table 1 may be used for the graphs in items 1($b$) and
2 of Theorem 10. For example, the cases $(r,t,s)=(20,1,5)$ and
$(r,t,s)=(28,1,5)$ in Fig. 2(h–i) are representable as in Table 2, where,
instead of $\circ$ standing for each vertex, we set the vertex notation of
Fig. 2(h–i). Here the four colors are indicated as in Fig. 2(d–j) and
Subsection 3.1. To distinguish the two cases in Table 2, note that the
4-cycles of $\\{4,4\\}_{20,1}^{5}$ (resp. $\\{4,4\\}_{28,1}^{5}$) have the
2-factors by color pairs $\\{1,2\\}$ and $\\{3,4\\}$ descending in zigzag from
right to left (resp. left to right), by alternate vector displacements
$(-1,0)$ (resp. $(1,0)$) for colors 1 and 3, and $(0,-1)$ for colors 2 and 4.
Generalizing and using the invariant notation of Remark 11, we can say that
the egc graphs in item 2(b) of Theorem 10 are as follows:

  1. 1.

$\\{4,4\\}_{6x+2,1}^{5}$ for $x>2$ has invariant $[a_{\swarrow
12,34},b_{\searrow 13,24},\searrow(2,4,1,3)]$;

  2. 2.

$\\{4,4\\}_{6x+4,1}^{5}$ for $x>2$ has invariant $[a_{\swarrow
13,24},b_{\searrow 12,34},\swarrow(2,4,3,1)]$.

As in Remark 11, we have here a distinguished oriented slanted arrow triple:
either $[_{\swarrow},_{\searrow},\searrow]$ or
$[_{\searrow},_{\swarrow},\swarrow]$. The graphs in item 2 of Theorem 10 admit
both invariants.

###  3.3 The bipartite complement of the Heawood graph

The bipartite complement $H$ of the Heawood-graph, with vertex set
$V(H)\\!=\\!\\{ij;i\in\\{+,-\\}$, $j\in\mathbb{Z}_{7}\\}$, is depicted on the
upper left of Fig. 4; its edges $\\{+j,-j\\}$, $\\{+j,-(j+2)\\}$,
$\\{+j,-(j+3)\\}$ and $\\{+j,-(j+4)\\}$, for $j\in\mathbb{Z}_{7}$, will be
denoted $jj$, $j(j+2)$, $j(j+3)$ and $j(j+4)$, respectively, where addition is
taken$\pmod{7}$. This yields the twenty-eight edges of $H$ as arcs from $+$ to
$-$ vertices. They form twenty-one 4-cycles $a_{i},b_{i},c_{i}$
($i\in\mathbb{Z}_{7}$) expressed, by omitting the signs $\pm$, as in Table 3.

Figure 4: Bipartite complement $H$ of the Heawood-graph and associated graph
${\rm GA}(H)$. $\begin{array}[]{|c|c|c|}\hline\cr
a_{0}=(00,30,33,03),&b_{0}=(00,50,52,02),&c_{0}=(02,62,63,03),\\\
a_{1}=(11,41,44,14),&b_{1}=(11,61,63,13),&c_{1}=(13,03,04,14),\\\
a_{2}=(22,52,55,25),&b_{2}=(22,02,04,24),&c_{2}=(24,14,15,25),\\\
a_{3}=(33,63,66,36),&b_{3}=(33,13,15,35),&c_{3}=(35,25,26,36),\\\
a_{4}=(44,04,00,40),&b_{4}=(44,24,26,46),&c_{4}=(46,36,30,40),\\\
a_{5}=(55,15,11,51),&b_{5}=(55,35,30,50),&c_{5}=(50,40,41,51),\\\
a_{6}=(66,26,22,62),&b_{6}=(66,46,41,61),&c_{6}=(61,51,52,62).\\\
\hline\cr\end{array}$ Table 3: The twenty-one 4-cycles $a_{i},b_{i},c_{i}$ of
$H$ ($i\in\mathbb{Z}_{7}$). Figure 5: Prisms of: truncated octahedron
$(32^{2}1)$, $K_{3,3}$ $(4^{3}3)$, $ST_{4}$ and 16-vertex graph ($31^{3}$).

This way, $jj=a_{j}\cap a_{j+4}\cap b_{j}$, $j(j+2)=b_{j}\cap b_{j+2}\cap
c_{j}$, $j(j+3)=a_{j}\cap c_{j}\cap c_{j+1}$ and $j(j+4)=a_{j+4}\cap
b_{j+2}\cap c_{j+1}$, $\forall j\in\mathbb{Z}_{7}$. We show there is no proper
edge coloring of $H$ that is tight on every 4-cycle. To prove this, we recur
to the bipartite graph ${\rm GA}(H)$ whose parts $V_{1}$ and $V_{2}$ are
respectively the twenty-eight edges of $H$ and the twenty-one 4-cycles of $H$,
with adjacency between an edge $ij$ of $H$ and a 4-cycle $C$ of $H$ whenever
$C$ passes through $ij$; ${\rm GA}(H)$ is represented in Fig. 4(b) with
$a_{i}$ written as $ai$ ($i=1,2,3$). A tight factorization of $H$ would be
equivalent to a 4-coloring of ${\rm GA}(H)$ that is monochromatic on each
vertex of $V_{1}$ but covering the four colors at the edges incident to each
vertex of $V_{2}$. We begin by coloring the edges incident to vertices
$00,02,03,04$ respectively with colors black, red, blue and green. This forces
the coloring of the subgraph of ${\rm GA}(H)$ in the lower left of Fig. 4. By
transferring this coloring to the representation of ${\rm GA}(H)$ on the right
of Fig. 4, as shown, it is verified that vertex 15 on the bottom of the
representation does not admit properly any of the four used colors.

##  4 Prisms of girth-g-regular graphs, g larger than 3

Given a graph $\Gamma^{\prime}$, the prism graph ${\rm
Prism}(\Gamma^{\prime})$ of $\Gamma^{\prime}$ is the graph cartesian product
$K_{2}\square\Gamma^{\prime}$. The cases of
$(e_{1})(e_{2})(e_{3})(e_{4})$-graphs with $(e_{1})(e_{2})(e_{3})(e_{4})$
$\neq 1^{4}$, apart from those treated in Section 3, are the prisms
$\Gamma=Prism(\Gamma^{\prime})$ of $(e_{1})(e_{2})(e_{3})$-graphs
$\Gamma^{\prime}$. It is easy to see that there is no egc graoh $\Gamma$ if
$g(\Gamma^{\prime})$ is odd.

Figure 6: A Pappus-graph cutout and the Desargues, Nauru and Dyck graph
prisms.

######  Conjecture 12.

Graphs $\Gamma$ with signatures $32^{2}1$ and $4^{3}3$ are not egc.

######  Example 13.

Conjecture 12 is sustained by the exhaustive partial colorings of the prisms
of the 24-vertex truncated octahedral graph [8, pp. 79–86] in Fig. 5(a–g) and
of the 6-vertex Thomsen graph ($K_{3,3}$) [7] in Fig. 5(h), which are
respectively a $32^{2}1$-graph and a $4^{3}3$-graph, with the incidental
obstructions indicated by a notification ”No!” in each case. Such exhaustive
partial colorings can be found similarly for example in the 120-vertex
truncated-icosidodecahedral graph [8, pp. 97–99].

Figure 7: An edge-girth coloring of the prism of $\\{6,3\\}_{|4,4|}$ on the
Klein bottle.

######  Remark 14.

A $31^{3}$-graph $\Gamma=K_{2}\square\Gamma^{\prime}$, where $\Gamma^{\prime}$
is a toroidal quotient graph of the hexagonal tessellation [4, 5] (i.e. the
tiling of the plane with Schläfli symbol $\\{6,3\\}$), may be an egc
$31^{3}$-graph. This is exemplified in Fig. 5(i–j), namely for the prisms of
the 24-vertex star graph $ST_{4}$ (with twelve girth 6-cycles) [9] and a
16-vertex graph (with just eight girth 6-cycles). But $\Gamma^{\prime}$ cannot
be the Pappus graph. Let us see why. A cutout in this case, as in Fig. 6(a)
(with octodecimal vertex notation and proper face coloring) contains nine
hexagonal tiles. In order to use the specified coloring to guarantee the
existence of an egc-graph, the “period” employed when moving from any
particular vertex $v_{R}$ of a cutout $R$ in any of the three directions
perpendicular to the edges of the tessellation – i.e., the number of tiles met
until a similar vertex $v_{R^{\prime}}$ in a cutout $R^{\prime}$ adjacent to
$R$ is reached – must be even, but 9 is odd.

######  Remark 15.

In the setting of Remark 14, by considering the junction of three hexagonal
prisms $P_{1},P_{2},P_{3}$, it is seen that in any such $P_{i}$ ($i=1,2,3$),
two edges not belonging to a hexagon can only be of the same color if their
endpoints are antipodal in the two hexagons of $P_{i}$. Up to automorphism and
permutation of colors, this allows for two distinct colorings of the hexagonal
prisms:

  1. 1.

the one as in both instances of Fig. 5(i–j) (with one color appearing on six
edges and the remaining four colors appearing each on four edges), and

  2. 2.

one with two colors appearing each on five edges and the other two colors
appearing each on four edges.

See Fig. 7, depicting a cutout of an egc-graph on the Klein bottle, namely an
edge-girth coloring of the prism of $\\{6,3\\}_{|4,4|}$ [23] on the Klein
bottle. In Fig. 7, the colorings of the hexagonal prisms in which one color
appears six times only occur in the first row, and no edge-girth coloring of
this graph is possible if only such colorings are used. Computational evidence
has been obtained that gives support to the following conjectures.

######  Conjecture 16.

The condition of even periods in Remark 14 is sufficient for the case of
prisms of hexagonal tessellations of the torus.

######  Conjecture 17.

The prisms of the hexagonal tessellations of the Klein bottle [23] are egc if
the cutout contains $m\times n$ tiles, with $m$ and $n$ even, and having both
types of colorings of the hexagonal prism as in Remark 15.

######  Example 18.

Conjecture 17 is sustained by the prism cutout in Fig. 7, showing an edge-
girth coloring of the prism of $\\{6,3\\}_{|4;4|}$ [23] on the Klein bottle.
Note that the colorings of the hexagonal prisms in which one color appears six
times only occur in the first row, and no edge-girth coloring of this graph is
possible if only such colorings are used.

Figure 8: Tutte 8-cage 3$1^{3}$-graph prism and 96-vertex cubic
$\Gamma^{\prime}$.

######  Example 19.

In Fig. 6(b), the prism of the Desargues graph on twenty vertices is shown
non-egc via obstructions by pairs of forced “long” parallel red edges.
However, in Fig. 6(c–d) the Nauru and Dyck graphs on twenty-four and thirty-
two vertices, respectively, are shown to have their prisms as egc graphs by
means of corresponding tight factorizations.

######  Example 20.

For the case $g(\Gamma^{\prime})=8$, let us consider $\Gamma^{\prime}$ to be
the Tutte 8-cage on 30 vertices. Fig. 8(a–c) shows why its $31^{3}$-graph
prism is not egc, with five 8-cycle prisms $K_{2}\square C_{8}$ in $\Gamma$
(presented cyclically mod 5), each of whose vertices should have its four
incident edges colored differently. Fig. 8 presents exhaustively and without
loss of generality partial edge-colorings in $\Gamma$, with copies of
$K_{2}\square C_{8}$ edge-colored accordingly and notification “No!” if an
obstruction to edge-coloring continuation appears.

$\begin{array}[]{l}\\!\hskip 3.98337pt\bar{3}\hskip 13.11671pt\bar{3}\hskip
13.11671pt4\hskip 13.11671pt1\hskip 13.11671pt2\hskip 13.11671pt3\hskip
13.11671pt\bar{4}\hskip 13.11671pt\bar{3}\hskip 13.11671pt4\hskip
13.11671pt2\hskip 13.11671pt1\hskip 13.11671pt3\hskip 13.11671pt\bar{4}\hskip
13.11671pt\bar{4}\hskip 13.11671pt3\hskip 13.11671pt2\hskip 13.11671pt1\hskip
13.11671pt4\hskip 13.11671pt\bar{3}\hskip 13.11671pt\bar{4}\hskip
13.11671pt3\hskip 13.11671pt1\hskip 13.11671pt2\hskip 13.11671pt4\\\
\\!\,\,\circ\,4\hskip 0.95319pt\circ\hskip 0.95319pt1\hskip
0.95319pt\circ\hskip 0.95319pt2\hskip 0.95319pt\circ\hskip 0.95319pt3\hskip
0.95319pt\circ\hskip 0.95319pt4\hskip 0.95319pt\circ\hskip 0.95319pt1\hskip
0.95319pt\circ\hskip 0.95319pt2\hskip 0.95319pt\circ\hskip 0.95319pt1\hskip
0.95319pt\circ\hskip 0.95319pt3\hskip 0.95319pt\circ\hskip 0.95319pt4\hskip
0.95319pt\circ\hskip 0.95319pt2\hskip 0.95319pt\circ\hskip 0.95319pt1\hskip
0.95319pt\circ\hskip 0.95319pt3\hskip 0.95319pt\circ\hskip 0.95319pt2\hskip
0.95319pt\circ\hskip 0.95319pt1\hskip 0.95319pt\circ\hskip 0.95319pt4\hskip
0.95319pt\circ\hskip 0.95319pt3\hskip 0.95319pt\circ\hskip 0.95319pt2\hskip
0.95319pt\circ\hskip 0.95319pt1\hskip 0.95319pt\circ\hskip 0.95319pt2\hskip
0.95319pt\circ\hskip 0.95319pt4\hskip 0.95319pt\circ\hskip 0.95319pt3\hskip
0.95319pt\circ\hskip 0.95319pt1\hskip 0.95319pt\circ\hskip 0.95319pt2\\\
\\!\,1\hskip 1.99168pt\square\hskip 1.99168pt2\hskip 1.99168pt\square\hskip
1.99168pt3\hskip 1.99168pt\square\hskip 1.99168pt4\hskip
1.99168pt\square\hskip 1.99168pt1\hskip 1.99168pt\square\hskip
1.99168pt2\hskip 1.99168pt\square\hskip 1.99168pt3\hskip
1.99168pt\square\hskip 1.99168pt4\hskip 1.99168pt\square\hskip
1.99168pt2\hskip 1.99168pt\square\hskip 1.99168pt1\hskip
1.99168pt\square\hskip 1.99168pt3\hskip 1.99168pt\square\hskip
1.99168pt4\hskip 1.99168pt\square\hskip 1.99168pt2\hskip
1.99168pt\square\hskip 1.99168pt1\hskip 1.99168pt\square\hskip
1.99168pt4\hskip 1.99168pt\square\hskip 1.99168pt3\hskip
1.99168pt\square\hskip 1.99168pt2\hskip 1.99168pt\square\hskip
1.99168pt1\hskip 1.99168pt\square\hskip 1.99168pt4\hskip
1.99168pt\square\hskip 1.99168pt3\hskip 1.99168pt\square\hskip
1.99168pt1\hskip 1.99168pt\square\hskip 1.99168pt2\hskip
1.99168pt\square\hskip 1.99168pt4\hskip 1.99168pt\square\hskip
1.99168pt3\hskip 1.99168pt\square\\\ \\!\,\,\circ\,3\hskip
0.95319pt\circ\hskip 0.95319pt4\hskip 0.95319pt\circ\hskip 0.95319pt1\hskip
0.95319pt\circ\hskip 0.95319pt2\hskip 0.95319pt\circ\hskip 0.95319pt3\hskip
0.95319pt\circ\hskip 0.95319pt4\hskip 0.95319pt\circ\hskip 0.95319pt1\hskip
0.95319pt\circ\hskip 0.95319pt3\hskip 0.95319pt\circ\hskip 0.95319pt4\hskip
0.95319pt\circ\hskip 0.95319pt2\hskip 0.95319pt\circ\hskip 0.95319pt1\hskip
0.95319pt\circ\hskip 0.95319pt3\hskip 0.95319pt\circ\hskip 0.95319pt4\hskip
0.95319pt\circ\hskip 0.95319pt3\hskip 0.95319pt\circ\hskip 0.95319pt2\hskip
0.95319pt\circ\hskip 0.95319pt1\hskip 0.95319pt\circ\hskip 0.95319pt4\hskip
0.95319pt\circ\hskip 0.95319pt3\hskip 0.95319pt\circ\hskip 0.95319pt2\hskip
0.95319pt\circ\hskip 0.95319pt4\hskip 0.95319pt\circ\hskip 0.95319pt3\hskip
0.95319pt\circ\hskip 0.95319pt1\hskip 0.95319pt\circ\hskip 0.95319pt2\hskip
0.95319pt\circ\hskip 0.95319pt4\\\ \\!\hskip 3.98337pt\bar{2}\hskip
13.11671pt\bar{1}\hskip 13.11671pt2\hskip 13.11671pt3\hskip 13.11671pt4\hskip
13.11671pt1\hskip 13.11671pt\bar{2}\hskip 13.11671pt\bar{2}\hskip
13.11671pt1\hskip 13.11671pt3\hskip 13.11671pt4\hskip 13.11671pt2\hskip
13.11671pt\bar{1}\hskip 13.11671pt\bar{2}\hskip 13.11671pt1\hskip
13.11671pt4\hskip 13.11671pt3\hskip 13.11671pt2\hskip 13.11671pt\bar{1}\hskip
13.11671pt\bar{1}\hskip 13.11671pt2\hskip 13.11671pt4\hskip 13.11671pt3\hskip
13.11671pt1\\\ \end{array}$ Table 4: Representing a coloring of 8-cycle prisms
$\Theta_{i}$ ($i=1,2,3,4$).

On the other hand, Table 4 uses the notation of Table 1 in representing a
coloring of the union $U$ of almost four (namely $3\frac{3}{4}$) contiguous
8-cycle prisms $\Theta_{i}$ ($i=1,2,3,4$) and the resulting forced colors for
the departing edges away from $U$. In Table 4, the middle row sequence, call
it $\Upsilon$, (obtained by disregarding the symbols “$\square$”, or replacing
them by commas) represents the subsequences of colors of the edges
$\\{(0,u),(1,u)\\}$ in the prisms $\Theta_{i}$, namely the subsequences
$\Upsilon_{1}=(1,2,3,4)^{2}$, $\Upsilon_{2}=(3,4,2,1)^{2}$,
$\Upsilon_{3}=(2,1,4,3)^{2}$ and $\Upsilon_{4}=(4,3,1,2)^{2}$. Here, the last
two terms of each $\Upsilon_{i}$ coincide (i.e. are shared) with the first two
terms of its subsequent $\Upsilon_{i+1}$, where the last 6-term subsequence is
completed to $\Upsilon_{4}$ by adding the first two terms of $\Upsilon_{1}$,
so $\Upsilon_{1}$ may be considered as the next $\Upsilon_{i}$ after the last
$\Upsilon_{4}$ (and explaining the fraction $3\frac{3}{4}$ mentioned above).
This suggest that $\Upsilon$ can be concatenated with itself a number $\ell$
of times to close a $(24\times\ell)$-cycle of colors for the edges
$(\\{0,u),(1,u)\\}$ of a Hamilton-cycle (of $\Gamma^{\prime}$) prism $H$ which
may be completed to an egc graph $\Gamma$ by means of the following
considerations. (An adequately colored graph $\Gamma^{\prime}$ is obtained
from Fig. 8(d) by adding a suitable colored outer cycle, missing in the
figure).

On the top and bottom rows of Table 4, the colors 1, 2, 3 and 4 with a bar on
top are those of the “long” edges in the four prisms $\Theta_{i}$ that close
the two 8-cycles in each $\Theta_{i}$. The remaining (non-barred) colors
suggest that the corresponding edges form external 4-cycles that may be joined
with $H$ to form a $\Gamma$ as desired. The “even longer” edges of these
external 4-cycles must be set to form (with two edges of the form
$\\{(0,u),(1,u)\\}$) new 4-cycles and can be selected to form the desired
$\Gamma$ by taking the number of concatenated copies of $U$ to be $\ell=4$, so
that $|V(\Gamma)|=192$. The two columns in Table 4 whose transpose rows are
“$4\circ 3\circ 2$” and “$4\circ\\!1\\!\circ\\!2$”, namely the third leftmost
and seventh rightmost $\square$-free columns, integrate one such 4-cycle. The
leftmost third, fourth, fifth and sixth columns are paired this way with the
rightmost seventh, eighth, ninth and tenth columns, but the last three pairs
must be paired with similar columns in the second, third and fourth version of
Table 4 (for indices $k\in\\{2,3,4=\ell\\}$ of copies $U_{k}$ of $U$, if we
agree that the leftmost third and rightmost seventh columns above are both for
$k=1$ and $U=U_{k}=U_{1}$). The same treatment can be set from the leftmost
ninth, tenth, eleventh and twelveth respectively to the rightmost first,
second, third and fourth columns, which also correspond in pairs that form
again “long” 4-cycles.

######  Theorem 21.

For each $4\leq k\in\mathbb{Z}$, there is an egc $31^{3}$-graph $\Gamma$ with
$192\times k$ edges as a prism of a hamiltonian cubic graph $\Gamma^{\prime}$
on $96\times k$ vertices based on $g$ contiguous copies of the edge-colored
subgraph in Table 4. However, the Tutte 8-cage is a non-egc $31^{3}$-graph.

###### Proof.

The argument above the statement can be completed for the case $k=1$. By
concatenating the graph from Table 4 any multiple of $g$ times, one extends
the construction. ∎

######  Remark 22.

Cubic graphs [16] on less than one hundred vertices, girth 10 and egc prisms
are CubicVT[80,30], CubicVT[96,34], CubicVT[96,49], CubicVT[96,50],
CubicVT[96,62].

##  5 Egc 1111-graphs

A construction [18, 24] of $1^{4}$-graphs, also called girth-tight, is as
follows. Let $\Gamma$ be 4-regular and let $\mathcal{C}$ be a partition of
$E(\Gamma)$ into cycles. The pair $(\Gamma,{\mathcal{C}})$ is a cycle
decomposition of $\Gamma$. Two edges of $\Gamma$ are opposite at vertex $v$ if
both are incident to $v$ and belong to the same element of $\mathcal{C}$. The
partial line graph $\mathbb{P}(\Gamma,{\mathcal{C}})$ of
$(\Gamma,{\mathcal{C}})$ is the graph with the edges of $\Gamma$ as vertices,
and any two such vertices adjacent if they share, as edges, a vertex of
$\Gamma$ and are not opposite at that vertex. A cycle $C$ in $\Gamma$ is
$\mathcal{C}$-alternating if no two consecutive edges of $C$ belong to the
same element of $\mathcal{C}$. Lemma 4.10 [18] says that
$\mathbb{P}(\Gamma,{\mathcal{C}})$ is girth-tight if and only if
$(\Gamma,{\mathcal{C}})$ contains neither $\mathcal{C}$-alternating cycles nor
triangles, except those contained in $\mathcal{C}$.

Figure 9: Tight factorizations of $\mathbb{P}(W(5,2))$, $\mathbb{P}(W(7,2))$
and $\mathbb{P}(W(6,2))$.

######  Remark 23.

As initial example of a partial line graph, consider the wreath graph
$W(n,2)=C_{n}[\overline{K_{2}}]$ ($n>4$), where $C_{n}$ is a cycle
$(v_{0},v_{1},\ldots,v_{n-1})$. Consider the partition $\mathcal{C}$ of
$W(n,2)$ into the 4-cycles $((v_{i},0),(v_{i+1},0),(v_{i},1),(v_{i+1},1))$
($i\in\mathbb{Z}_{n}$). These form a decomposition $(W(n,2),{\mathcal{C}})$,
which yields the partial line graph $\mathbb{P}(W(n,2),{\mathcal{C}})$. We
prove now that for all values of $n$, $\mathbb{P}(W(n,2),{\mathcal{C}})$ is
egc, as in Fig. 9(a–c), where $\mathbb{P}(W(5,2),{\mathcal{C}})$,
$\mathbb{P}(W(7,2))$ and $\mathbb{P}(W(6,2),{\mathcal{C}})$ are represented
showing tight factorizations via edge colors 1, 2, 3, 4.

######  Theorem 24.

Let $4<n\in\mathbb{Z}$. Then, $\mathbb{P}(W(n,2),{\mathcal{C}})$ is egc.

###### Proof.

Each vertex $((v_{i},j)(v_{i\pm 1},j^{\prime}))$ of
$\mathbb{P}(W(n,2),{\mathcal{C}})$ representing the edge between the vertices
$(v_{i},j)$ and $(v_{i\pm 1},j^{\prime})$ of $W(n,2)$, where
$i\in\mathbb{Z}_{n}$ and $j,j^{\prime}\in\\{0,1\\}$, will be denoted
$(i_{j}(i\pm 1)_{j^{\prime}})$. We use modifications of Lemma 9 separately for
the cases of odd and even $n$. If $n=2k+1$ is odd, then we have a
2-factorization of $\mathbb{P}(W(n,2),{\mathcal{C}})$, one of whose two
2-factors is composed by three disjoint even-length cycles not sharing more
than two edges with any 4-cycle, namely one of length 8 and two of length
$4k+2$, specifically

$\begin{array}[]{l}((\\!-k_{0}k_{0})(\\!-k_{0}(1\\!-k)_{1})(\\!-k_{0}k_{1})((k\\!-1)_{0}k_{1})(-k_{1}k_{1})(\\!-k_{1}(1\\!-k)_{0})(\\!-k_{1}k_{0})((k\\!-1)1k_{0}));\\\
((\\!-k_{0}(1\\!-k)_{0})\cdots(\\!-1_{0}0_{0})(0_{0}1_{0})\cdots((k\\!-1)_{0}k_{0})(k_{0}(k\\!-1)_{1})\cdots(1_{1}0_{1})(0_{1}-1_{1})\cdots(k_{1}-k_{0}));\\\
((\\!-k_{1}(1\\!-k)_{1})\cdots(-1_{1}0_{1})(0_{1}1_{1})\cdots((k\\!-1)_{1}k_{1})(k_{1}(k\\!-1)_{0})\cdots(1_{0}0_{0})(0_{0}-1_{0})\cdots(k_{0}\\!-k_{1})),\\\
\end{array}$

which for $k=2$ and $k=3$ can be visualized respectively in Fig. 9(a) and Fig.
9(b) as three alternate-red-blue cycles, one of length 8 and 2 of length
$4k+2$. The other 2-factor also is formed by even cycles not sharing more than
two edges with any 4-cycle, viewable as alternate-green-hazel cycles for $k=2$
in Fig. 9(a) and for $k=3$ in Fig. 9(b). This 2-factor has reflective
$\mathbb{Z}_{2}$ symmetry on a vertical axis. As for the mentioned
modifications of Lemma 9, note that the two cycles of length $4k+2$ for $k$
odd and for $k$ even differ: If $k$ is odd, the two cycles of length $2k+2$
contain opposite edges in the 4-cycles, while if $k$ is even, the two cycles
of length $2k+2$ share just one edge with each 4-cycle. Both cases refine into
corresponding tight 1-factorizations. In particular, if $n=2k$ is even, then a
2-factorization of $\mathbb{P}(W(n,2),{\mathcal{C}})$ is formed by $k$ cycles
of length 8 forming a class of cycles$\pmod{k}$, namely

$(\\!(i_{0}(i\\!+1)_{0}\\!)(\\!(i\\!+1)_{0}(i\\!+2)_{0}\\!)(\\!(i\\!+2)_{0}(i\\!+1)_{1}\\!)(\\!(i\\!+1)_{1}i_{0}\\!)(\\!(i\\!+1)_{1}i_{1}\\!)(\\!(i\\!+1)_{1}(i\\!+2)_{1})(\\!(i\\!+2)_{1}(i\\!+1)_{0})(\\!(i\\!+1_{0})i_{1})\\!),$

where $i$ is odd, $0<i<n$. The other 2-factor also is formed by 8-cycles, see
Fig. 9(c). ∎

A particular case of a cycle decomposition is that of a linking-ring structure
[24], that works for two colors, say red and green. This structure applies in
the following paragraphs only for $n$ even; (if $n$ is odd, then more than two
colors would be needed in order to distinguish adjacent cycles of the
decomposition $(W(n,2),{\mathcal{C}})$). A Linking-ring structure is defined
as follows. An isomorphism between two cycle decompositions
$(\Gamma_{1},{\mathcal{C}}_{1})$ and $(\Gamma_{2},{\mathcal{C}}_{2})$ is an
isomorphism $\xi:\Gamma_{1}\rightarrow\Gamma_{2}$ such that
$\xi({\mathcal{C}}_{1})={\mathcal{C}}_{2}$. An isomorphism $\xi$ from a cycle
decomposition to itself is an automorphism, written $\xi\in
Aut(\Gamma,{\mathcal{C}})$. A cycle decomposition $(\Gamma,{\mathcal{C}})$ is
flexible if for every vertex $v$ and each edge $e$ incident to $v$ there is
$\xi\in Aut(\Gamma,{\mathcal{C}})$ such that:

  1. (I)

$\xi$ fixes each vertex of the cycle in ${\mathcal{C}}$ containing $e$ and

  2. (II)

$\xi$ interchanges the two other neighbors of $v$; the edges joining $v$ to
those neighbors are in some other cycle of $\mathcal{C}$.

A cycle decomposition $(\Gamma,{\mathcal{C}})$ is bipartite if $\mathcal{C}$
can be partitioned into two subsets $\mathcal{G}$ (green) and $\mathcal{R}$
(red) so that each vertex of $\Gamma$ is in one cycle of $\mathcal{G}$ and one
cycle of $\mathcal{R}$.

The largest subgroup of ${\rm Aut}(\Gamma,{\mathcal{C}})$ preserving each of
the sets $\mathcal{G}$ and $\mathcal{R}$ is denoted ${\rm
Aut}^{+}(\Gamma,{\mathcal{C}})$. In a bipartite cycle decomposition, an
element of ${\rm Aut}(\Gamma,{\mathcal{C}})$ either interchanges $\mathcal{G}$
and $\mathcal{R}$ or preserves each of $\mathcal{G}$ and $\mathcal{R}$ set-
wise, so it is contained in ${\rm Aut}^{+}(\Gamma,{\mathcal{C}})$.

This shows that the index of ${\rm Aut}^{+}(\Gamma,{\mathcal{C}})$ in ${\rm
Aut}(\Gamma,{\mathcal{C}})$ is at most 2. If this index is 2, then we say that
$(\Gamma,{\mathcal{C}})$ is self-dual; this happens if and only if there is
$\sigma\in Aut(\Gamma,{\mathcal{C}})$ such that
${\mathcal{G}}\sigma={\mathcal{R}}$ and ${\mathcal{R}}\sigma={\mathcal{G}}$.
In [18], a cycle decomposition $(\Gamma,{\mathcal{C}})$ is said to be a
linking-ring (LR) structure if it is

  1. (i)

bipartite,

  2. (ii)

flexible and

  3. (iii)

${\rm Aut}^{+}(\Gamma,{\mathcal{C}})$ acts transitively on $V(\Gamma)$.

However, there are tight factorizations of graphs
$\mathbb{P}(\Gamma,{\mathcal{P}})$ obtained by relaxing condition (iii) in
that definition. So we will say that a cycle decomposition
$(\Gamma,{\mathcal{P}})$ is a relaxed LR structure if it satisfies just
conditions (i) and (ii).

Figure 10: Tight factorizations of (a) $\mathbb{P}({\rm Br}(4,5;2))$ and (b)
$\mathbb{P}({\rm MBr}(4,8;3))$.
$\begin{array}[]{|c|c|c|c|}\hline\cr(0^{0}_{1}[a]^{0}_{1}1[b]0^{1}_{2}[c]^{3}_{0}1[d])&(1^{0}_{2}[a]^{1}_{2}2[b]1^{2}_{4}[c]^{0}_{1}2[d])&(2^{0}_{1}[a]^{2}_{3}1[b]2^{1}_{2}[c]^{1}_{2}1[d])&(3^{0}_{2}[a]^{3}_{0}2[b]3^{2}_{4}[c]^{2}_{3}2[d])\\\
(0^{1}_{2}[a]^{0}_{1}2[b]0^{2}_{3}[c]^{3}_{0}2[d])&(1^{1}_{3}[a]^{1}_{2}3[b]1^{3}_{0}[c]^{0}_{1}3[d])&(2^{1}_{2}[a]^{2}_{3}2[b]2^{2}_{3}[c]^{1}_{2}2[d])&(3^{1}_{3}[a]^{3}_{0}3[b]3^{3}_{0}[c]^{2}_{3}3[d])\\\
(0^{2}_{3}[a]^{0}_{1}3[b]0^{3}_{4}[c]^{3}_{0}3[d])&(1^{2}_{4}[a]^{1}_{2}4[b]1^{4}_{1}[c]^{0}_{1}4[d])&(2^{2}_{3}[a]^{2}_{3}3[b]2^{3}_{4}[c]^{1}_{2}3[d])&(3^{2}_{4}[a]^{3}_{0}4[b]3^{4}_{1}[c]^{2}_{3}4[d])\\\
(0^{3}_{4}[a]^{0}_{1}4[b]0^{4}_{0}[c]^{3}_{0}4[d])&(1^{3}_{0}[a]^{1}_{2}0[b]1^{0}_{2}[c]^{0}_{1}0[d])&(2^{3}_{4}[a]^{2}_{3}4[b]2^{4}_{0}[c]^{1}_{2}4[d])&(3^{3}_{0}[a]^{3}_{0}0[b]3^{0}_{2}[c]^{2}_{3}0[d])\\\
(0^{4}_{0}[a]^{0}_{1}0[b]0^{0}_{1}[c]^{3}_{0}0[d])&(1^{4}_{1}[a]^{1}_{2}1[b]1^{1}_{3}[c]^{0}_{1}1[d])&(2^{4}_{0}[a]^{2}_{3}0[b]2^{0}_{1}[c]^{1}_{2}0[d])&(3^{0}_{1}[a]^{3}_{0}1[b]3^{1}_{3}[c]^{2}_{3}1[d])\\\
\hline\cr\end{array}$ Table 5: A code representation of the tight
factorization in Fig. 10(a).

######  Remark 25.

With the aim of yielding semisymmetric graphs from LR structures, [24]
defines:

  1. (a)

the barrel ${\rm Br}(k,n;r)$, where $4\leq k\equiv 0\pmod{2}$, $n\geq 5$,
$r^{2}\equiv\pm 1\pmod{n}$, $r\not\equiv\pm 1\pmod{n}$ and $0\leq
r<\frac{n}{2}$, as the graph with vertex set
$\mathbb{Z}_{k}\times\mathbb{Z}_{n}$ and $(i,j)$ red-adjacent to $(i\pm 1,j)$
and green-adjacent to $(i,j\pm r^{i})$;

  2. (b)

the mutant barrel ${\rm MBr}(k,n;r)$, where $2\leq k\equiv n\equiv 0\pmod{2}$,
$n\geq 6$, $r^{2}\equiv\pm 1\pmod{n}$ and $r\not\equiv\pm 1\pmod{n}$, as the
graph with vertex set $\mathbb{Z}_{k}\times\mathbb{Z}_{n}$ and $(i,j)$ red-
adjacent to $(i+1,j)$ for $0\leq i<k-1$, $(k-1,j)$ red-adjacent to
$(0,j+\frac{n}{2})$, and $(i,j)$ green-adjacent to $(i,j\pm r^{i})$.

Figure 11: Egc $\mathbb{P}({\rm Br}(3,F))$ for the three 2-factorizations $F$
of $K_{7}$.

Fig. 10(a) (resp. 10(b)) represents $\mathbb{P}({\rm Br}(4,5;2))$ (resp.
$\mathbb{P}({\rm MBr}(4,8;3))$), where each vertex $(i,j)$ is denoted $ij$,
vertices $i0$ appear twice (on top and bottom), red edges are shown in thin
trace, green edges arising from the cycles $F_{1}^{5}=(0,1,2,3,4)$ and
$F_{2}^{5}=(0,2,4,1,3)$ of $K_{5}$ (resp. $F_{1}^{8}=(0,1,2,3,4,5,6,7)$ and
$F_{3}^{8}=(0,3,6,1,4,7,2,5)$ of $K_{8}$) in thin and dashed trace,
respectively, and the edges of the corresponding partial line graphs in thick
trace on the colors orange = $a$, black = $b$, hazel = $c$ and blue = $d$,
setting a tight factorization. Vertices of green and red cycles are said to be
green and red, respectively. To the left of these two graphs in Fig. 10, the
corresponding green and red-green subgraphs are shown.

Figure 12: Tight factorization of $\mathbb{P}({\rm
MBr}(3,\\{F_{1}^{8},F_{2}^{8},F_{3}^{8}\\}))$, based on 2-factors of $K_{8}$.

$\begin{array}[]{|c|c|c|}\hline\cr(0^{0}_{1}[a]^{0}_{1}1[b]0^{1}_{2}[c]^{2}_{0}1[d])&(1^{0}_{2}[c]^{0}_{1}2[d]1^{2}_{4}[a]^{1}_{2}2[b])&(2^{0}_{3}[a]^{2}_{0}3[b]2^{3}_{6}[c]^{1}_{2}3[d])\\\
(0^{1}_{2}[a]^{0}_{1}2[b]0^{2}_{3}[c]^{2}_{0}2[d])&(1^{1}_{3}[c]^{0}_{1}3[d]1^{3}_{5}[a]^{1}_{2}3[b])&(2^{1}_{4}[a]^{2}_{0}4[b]2^{4}_{0}[c]^{1}_{2}4[d])\\\
(0^{2}_{3}[a]^{0}_{1}3[b]0^{3}_{4}[c]^{2}_{0}3[d])&(1^{2}_{4}[c]^{0}_{1}4[d]1^{4}_{6}[a]^{1}_{2}4[b])&(2^{2}_{5}[a]^{2}_{0}5[b]2^{5}_{1}[c]^{1}_{2}5[d])\\\
(0^{3}_{4}[a]^{0}_{1}4[b]0^{4}_{5}[c]^{2}_{0}4[d])&(1^{3}_{5}[c]^{0}_{1}5[d]1^{5}_{0}[a]^{1}_{2}5[b])&(2^{3}_{6}[a]^{2}_{0}6[b]2^{6}_{2}[c]^{1}_{2}6[d])\\\
(0^{4}_{5}[a]^{0}_{1}5[b]0^{5}_{6}[c]^{2}_{0}5[d])&(1^{4}_{6}[c]^{0}_{1}6[d]1^{6}_{1}[a]^{1}_{2}6[b])&(2^{4}_{0}[a]^{2}_{0}0[b]2^{0}_{3}[c]^{1}_{2}0[d])\\\
(0^{5}_{6}[a]^{0}_{1}6[b]0^{6}_{0}[c]^{2}_{0}6[d])&(1^{5}_{0}[c]^{0}_{1}0[d]1^{0}_{2}[a]^{1}_{2}0[b])&(2^{5}_{1}[a]^{2}_{0}1[b]2^{1}_{4}[c]^{1}_{2}1[d])\\\
(0^{6}_{0}[a]^{0}_{1}0[b]0^{0}_{1}[c]^{2}_{0}0[d])&(1^{6}_{1}[c]^{0}_{1}1[d]1^{1}_{3}[a]^{1}_{2}1[b])&(2^{6}_{2}[a]^{2}_{0}2[b]2^{2}_{5}[c]^{1}_{2}2[d])\\\
\hline\cr\end{array}$

$\begin{array}[]{|c|c|c|}\hline\cr(0^{0}_{1}[a]^{0}_{1}1[b]0^{1}_{5}[c]^{2}_{0}5[d])&(1^{1}_{2}[c]^{0}_{1}2[d]1^{2}_{0}[a]^{1}_{2}0[b])&(2^{2}_{3}[a]^{2}_{0}3[b]2^{3}_{1}[c]^{1}_{2}1[d])\\\
(0^{1}_{5}[a]^{0}_{1}5[b]0^{5}_{2}[c]^{2}_{0}2[d])&(1^{2}_{0}[c]^{0}_{1}0[d]1^{0}_{3}[a]^{1}_{2}3[b])&(2^{3}_{1}[a]^{2}_{0}1[b]2^{1}_{4}[c]^{1}_{2}4[d])\\\
(0^{5}_{2}[a]^{0}_{1}2[b]0^{2}_{4}[c]^{2}_{0}4[d])&(1^{0}_{3}[c]^{0}_{1}3[d]1^{3}_{5}[a]^{1}_{2}5[b])&(2^{1}_{4}[a]^{2}_{0}4[b]2^{4}_{0}[c]^{1}_{2}0[d])\\\
(0^{2}_{4}[a]^{0}_{1}4[b]0^{4}_{3}[c]^{2}_{0}3[d])&(1^{3}_{5}[c]^{0}_{1}5[d]1^{5}_{4}[a]^{1}_{2}4[b])&(2^{4}_{0}[a]^{2}_{0}0[b]2^{0}_{5}[c]^{1}_{2}5[d])\\\
(0^{4}_{3}[a]^{0}_{1}3[b]0^{3}_{6}[c]^{2}_{0}6[d])&(1^{5}_{4}[c]^{0}_{1}4[d]1^{4}_{6}[a]^{1}_{2}6[b])&(2^{0}_{5}[a]^{2}_{0}5[b]2^{5}_{6}[c]^{1}_{2}6[d])\\\
(0^{3}_{6}[a]^{0}_{1}6[b]0^{6}_{0}[c]^{2}_{0}0[d])&(1^{4}_{6}[c]^{0}_{1}6[d]1^{6}_{1}[a]^{1}_{2}1[b])&(2^{5}_{6}[a]^{2}_{0}6[b]2^{6}_{2}[c]^{1}_{2}2[d])\\\
(0^{6}_{0}[a]^{0}_{1}0[b]0^{0}_{1}[c]^{2}_{0}1[d])&(1^{6}_{1}[c]^{0}_{1}1[d]1^{1}_{2}[a]^{1}_{2}2[b])&(2^{6}_{2}[a]^{2}_{0}2[b]2^{2}_{3}[c]^{1}_{2}3[d])\\\
\hline\cr\end{array}$

$\begin{array}[]{|c|c|c|}\hline\cr(0^{0}_{1}[a]^{0}_{1}1[b]0^{1}_{6}[c]^{2}_{0}1[d])&(1^{0}_{3}[c]^{0}_{1}3[d]1^{3}_{1}[a]^{1}_{2}1[b])&(2^{0}_{2}[a]^{2}_{0}2[b]2^{2}_{1}[c]^{1}_{2}1[d])\\\
(0^{1}_{6}[a]^{0}_{1}6[b]0^{6}_{0}[c]^{2}_{0}6[d])&(1^{3}_{1}[c]^{0}_{1}1[d]1^{1}_{5}[a]^{1}_{2}5[b])&(2^{2}_{1}[a]^{2}_{0}1[b]2^{1}_{4}[c]^{1}_{2}4[d])\\\
(0^{6}_{0}[a]^{0}_{1}0[b]0^{0}_{1}[c]^{2}_{0}0[d])&(1^{1}_{5}[c]^{0}_{1}5[d]1^{5}_{0}[a]^{1}_{2}0[b])&(2^{1}_{4}[a]^{2}_{0}4[b]2^{4}_{0}[c]^{1}_{2}0[d])\\\
(0^{2}_{3}[a]^{0}_{1}3[b]0^{3}_{4}[c]^{2}_{0}3[d])&(1^{5}_{0}[c]^{0}_{1}0[d]1^{0}_{3}[a]^{1}_{2}3[b])&(2^{4}_{0}[a]^{2}_{0}0[b]2^{0}_{2}[c]^{1}_{2}2[d])\\\
(0^{3}_{4}[a]^{0}_{1}4[b]0^{4}_{5}[c]^{2}_{0}4[d])&(1^{2}_{4}[c]^{0}_{1}4[d]1^{4}_{6}[a]^{1}_{2}6[b])&(2^{3}_{5}[a]^{2}_{0}5[b]2^{5}_{6}[c]^{1}_{2}6[d])\\\
(0^{4}_{5}[a]^{0}_{1}5[b]0^{5}_{2}[c]^{2}_{0}5[d])&(1^{4}_{6}[c]^{0}_{1}6[d]1^{6}_{2}[a]^{1}_{2}2[b])&(2^{5}_{6}[a]^{2}_{0}6[b]2^{6}_{3}[c]^{1}_{2}3[d])\\\
(0^{5}_{2}[a]^{0}_{1}2[b]0^{2}_{3}[c]^{2}_{0}2[d])&(1^{6}_{2}[c]^{0}_{1}2[d]1^{2}_{4}[a]^{1}_{2}4[b])&(2^{6}_{3}[a]^{2}_{0}2[b]2^{3}_{5}[c]^{1}_{2}5[d])\\\
\hline\cr\end{array}$

Table 6: Code representations of $F_{1}^{7}$, $F_{2}^{7}$ and $F_{3}^{7}$.

Note that thick edges of colors orange and black form cycles zigzagging
between:

  1. (A)

the vertices of each vertical green cycle (excluding the rightmost green
cycle) and

  2. (B)

their adjacent red vertices to their immediate right.

Also, note that thick blue and hazel edges form cycles zigzagging between:

  1. (C)

the red vertices and

  2. (D)

the vertices of the next vertical green cycle to their right.

The girth is realized by tight 4-cycles (i.e., using the four colors) with a
pair of edges (blue and hazel) to the left of each vertical green cycle and
another pair of edges (black and red) to the corresponding right. This is
always attainable, because similar bicolored cycles can always we obtained,
generating the desired tight factorizations. For instance, assigning colors
$a,b,c,d$ to the edges $(i_{j}^{j+r^{i}},\,_{i}^{i+1}j)$,
$(i_{j}^{j+r^{i}},\,_{i}^{i+1}(j+r^{i}))$,
$((i+1)_{j}^{j+r^{i}},\,_{i}^{i+1}(j+r^{i}))$ and
$((i+1)_{j}^{j+r^{i}},\,_{i}^{i+1}j)$, respectively, yields a tight
factorization of $\mathbb{P}({\rm Br}(k,n;r))$.

$\begin{array}[]{|c|c|c|c|}\hline\cr(0^{0}_{1}[a]^{0}_{1}1[b]0^{1}_{2}[c]^{3}_{0}1[d])&(1^{0}_{2}[a]^{1}_{2}2[b]1^{2}_{4}[c]^{0}_{1}2[d])&(2^{0}_{3}[a]^{2}_{3}3[b]2^{3}_{6}[c]^{1}_{2}3[d])&(3^{0}_{4}[a]^{3}_{0}4[b]3^{4}_{8}[c]^{2}_{3}4[d])\\\
(0^{1}_{2}[a]^{0}_{1}2[b]0^{2}_{3}[c]^{3}_{0}2[d])&(1^{1}_{3}[a]^{1}_{2}3[b]1^{3}_{5}[c]^{0}_{1}3[d])&(2^{1}_{4}[a]^{2}_{3}4[b]2^{4}_{7}[c]^{1}_{2}4[d])&(3^{1}_{5}[a]^{3}_{0}5[b]3^{5}_{0}[c]^{2}_{3}5[d])\\\
(0^{2}_{3}[a]^{0}_{1}3[b]0^{3}_{4}[c]^{3}_{0}3[d])&(1^{2}_{4}[a]^{1}_{2}4[b]1^{4}_{6}[c]^{0}_{1}4[d])&(2^{2}_{5}[a]^{2}_{3}5[b]2^{5}_{8}[c]^{1}_{2}5[d])&(3^{2}_{6}[a]^{3}_{0}6[b]3^{6}_{1}[c]^{2}_{3}6[d])\\\
(0^{3}_{4}[a]^{0}_{1}4[b]0^{4}_{5}[c]^{3}_{0}4[d])&(1^{3}_{5}[a]^{1}_{2}5[b]1^{5}_{7}[c]^{0}_{1}5[d])&(2^{3}_{6}[a]^{2}_{3}6[b]2^{6}_{0}[c]^{1}_{2}6[d])&(3^{3}_{7}[a]^{3}_{0}7[b]3^{7}_{2}[c]^{2}_{3}7[d])\\\
(0^{4}_{5}[a]^{0}_{1}5[b]0^{5}_{6}[c]^{3}_{0}5[d])&(1^{4}_{6}[a]^{1}_{2}6[b]1^{6}_{8}[c]^{0}_{1}6[d])&(2^{4}_{7}[a]^{2}_{3}7[b]2^{7}_{1}[c]^{1}_{2}7[d])&(3^{0}_{8}[a]^{3}_{0}8[b]3^{8}_{3}[c]^{2}_{3}8[d])\\\
(0^{5}_{6}[a]^{0}_{1}6[b]0^{6}_{7}[c]^{3}_{0}6[d])&(1^{1}_{8}[a]^{1}_{2}7[b]1^{7}_{0}[c]^{0}_{1}7[d])&(2^{5}_{8}[a]^{2}_{3}8[b]2^{8}_{2}[c]^{1}_{2}8[d])&(3^{1}_{0}[a]^{3}_{0}0[b]3^{0}_{4}[c]^{2}_{3}0[d])\\\
(0^{6}_{7}[a]^{0}_{1}7[b]0^{7}_{8}[c]^{3}_{0}7[d])&(1^{2}_{0}[a]^{1}_{2}8[b]1^{8}_{1}[c]^{0}_{1}8[d])&(2^{6}_{0}[a]^{2}_{3}0[b]2^{0}_{3}[c]^{1}_{2}0[d])&(3^{2}_{1}[a]^{3}_{0}1[b]3^{1}_{5}[c]^{2}_{3}1[d])\\\
(0^{7}_{8}[a]^{0}_{1}8[b]0^{8}_{0}[c]^{3}_{0}8[d])&(1^{3}_{1}[a]^{1}_{2}0[b]1^{0}_{2}[c]^{0}_{1}0[d])&(2^{7}_{1}[a]^{2}_{3}1[b]2^{1}_{4}[c]^{1}_{2}1[d])&(3^{3}_{2}[a]^{3}_{0}2[b]3^{2}_{6}[c]^{2}_{3}2[d])\\\
(0^{8}_{0}[a]^{0}_{1}0[b]0^{0}_{1}[c]^{3}_{0}0[d])&(1^{4}_{2}[a]^{1}_{2}1[b]1^{1}_{3}[c]^{0}_{1}1[d])&(2^{8}_{2}[a]^{2}_{3}2[b]2^{2}_{5}[c]^{1}_{2}2[d])&(3^{0}_{1}[a]^{3}_{0}3[b]3^{3}_{7}[c]^{2}_{3}3[d])\\\
\hline\cr\end{array}$ Table 7: Tight factorization of $\mathbb{P}(4,F^{9})$.

A code representation of the tight factorization in Fig. 10(a) is given in
Table 5, where each green edge $\\{ij,i(j+r^{i})\\}$ in ${\rm Br}(k,n;r)$
yields a green vertex $i_{j}^{j+r^{i}}$ in $\mathbb{P}({\rm Br}(k,n;r))$, each
red edge $\\{ij,(i+1)j\\}$ in ${\rm Br}(k,n;r)$ yields a red vertex
${}_{i}^{i+1}j$ in $\mathbb{P}({\rm Br}(k,n;r))$, and the color of an edge
between a green vertex and a red vertex is indicated between brackets: $[a]$
for orange, $[b]$ for black, $[c]$ for hazel and $[d]$ for blue.

######  Remark 26.

Generalizing Remark 25 to get other egc girth-tight graphs, we consider a
2-factorization $F^{n}=\\{F_{1}^{n},F_{2}^{n},\ldots,F_{k-1}^{n}\\}$ of the
complete graph $K_{n}$, for odd $n=2k+1>6$ and use it to define the barrel
${\rm Br}(k,F^{n})$, with

  1. (i)

$\mathbb{Z}_{k}\times\mathbb{Z}_{n}$ as vertex set and

  2. (ii)

edges forming precisely red cycles $((0,i),(1,i),\ldots,(k-1,i))$, where
$i\in\mathbb{Z}_{n}$, and green subgraphs $\\{j\\}\times F_{j}^{n}$, where
$j\in\mathbb{Z}_{k}$.

Fig. 11 contains representations of $\mathbb{P}({\rm Br}(3,F^{7}))$ for three
distinct 2-factorizations $F^{7}$ of $K_{7}$, with tight factorizations
represented as in Fig. 10, with green cycles so that each vertex $(i,0)=i0$
appears just once (not twice, as in Fig. 10(a–b)). In the three cases,
$F_{1}^{7}$, $F_{2}^{7}$ and $F_{3}^{7}$, green edges are traced thick, thin
and dashed, respectively. To the left of these representations, the
corresponding green subgraphs are shown. Code representations of these three
tight factorizations can be found in Table 6, following the conventions of
Table 5. (A different 1-factorization of $K_{7}$ that may be used with the
same purpose is for example
$\\{(0,1,2,3,4,5,6),(0,3,5,1,6,2,4),(0,2,5)(1,3,6,4)$).

In the same way, by considering the 2-factorization given in $K_{9}$ seen as
the Cayley graph $C_{9}(1,2,3,4)$ with $F^{9}$ formed by the 2-factors
$F_{1}^{9},F_{2}^{9},F_{3}^{9},F_{4}^{9}$ generated by the respective colors
1, 2, 3, 4, namely Hamilton cycles $F_{1}^{9},F_{2}^{9},F_{4}^{9}$ but
$F_{3}^{9}=3K_{3}$, we get a tight factorization of $\mathbb{P}(4,F^{9})$.
This is encoded in Table 7 in a similar fashion to that of Tables 4–5.

If $n=2k$ is even, a similar generalization takes a 2-factorization
$F^{n}=\\{F_{1}^{n},$ $F_{2}^{n},\ldots,F_{k-2}^{n}\\}$ of
$K_{n}-\\{i(i+k);i=0,\ldots,k-1\\}$ and uses the 1-factor
$\\{i(i+k);i=0,\ldots,k-1\\}$ to get a generalized mutant barrel ${\rm
MBr}(k-1,F^{n})$ in a likewise fashion to that of item (b) in Remark 25 but
modified now via $F^{n}$, namely with

  1. (i’)

$\mathbb{Z}_{k-1}\times\mathbb{Z}_{n}$ as vertex set and

  2. (ii’)

edges forming precisely red cycles
$((0,i),(1,i),\ldots,(k-1,i),(0,i+\frac{n}{2}),(1,i+\frac{n}{2}),\ldots,(k-1,i+\frac{n}{2}))$,
where $i\in\mathbb{Z}_{n}$, and green subgraphs $\\{j\\}\times F_{j}^{n}$,
where $j\in\mathbb{Z}_{k}$.

Fig. 14 represents a tight factorization of $\mathbb{P}({\rm MBr}(3,F^{8}))$,
where $F^{8}=\\{F_{1}^{8},F_{2}^{8},F_{3}^{8}\\}$, represented on the upper
left of the figure, is such a 2-factorization, with $F_{1}^{8}$ and
$F_{3}^{8}$ as in Fig. 11, and $F_{2}^{8}=(0,2,4,6)(1,3,5,7)$, via
corresponding thick, thin and dashed, green edge tracing. On the lower left, a
representation of the red-green graph ${\rm MBr}(3,F^{8})$ is found.

We can further extend these notions of barrel and mutant barrel by taking a
cycle $G^{n}=(G_{1}^{n},G_{2}^{n},\ldots,G_{\ell}^{n})$ of copies of the
2-factors of $F^{n}$, where $G_{i}^{n}\in F^{n}$ but with no two contiguous
$G_{i}^{n}$ and $G_{i+1}^{n}\pmod{n}$ being the same element of $F^{n}$. Here,
$\ell\geq 3$. This defines a barrel ${\rm Br}(\ell,G^{n})$ or mutant barrel
${\rm MBr}(\ell,G^{n})$ ($n$ even in this case) and establishes the following.

######  Theorem 27.

The barrels and mutant barrels obtained in Remark 26 produce corresponding egc
graphs $\mathbb{P}({\rm Br}(\ell,G^{n}))$ and $\mathbb{P}({\rm
MBr}(\ell,G^{n}))$.

###### Proof.

The zigzagging orange-black and hazel-blue cycles between each pair of
contiguous green-vertex and red-vertex columns in the graphs of Fig. 10–12 are
as in Lemma 9. ∎

##  6 Egc girth-g-regular graphs, g larger than 4

######  Theorem 28.

We have the following:

  1. (a)

the $32$-vertex Armanios-Wells graph ${\rm AW}$ [1] [2, p. 266] is an egc
$(12)^{5}$-graphs;

  2. (b)

the $36$-vertex Sylvester graph ${\rm Syl}$ [2, p. 223] is a $8^{5}$-graph,
but is not egc.

###### Proof.

(a) The center of Fig. 13 represents ${\rm AW}$ colored as claimed. The
vertices of ${\rm AW}$ are denoted $Xi$ ($X\in\\{A,B,C,D\\}$;
$i\in\mathbb{Z}_{8}$). An edge-color assignment for ${\rm AW}$ is generated
mod 4 or$\pmod{\mathbb{Z}_{4}}$, where
$\mathbb{Z}_{4}=\\{0,2,4,6\\}\subset\mathbb{Z}_{8}$ is a subgroup and an ideal
of $\mathbb{Z}_{8}$, as follows:

$\displaystyle\begin{array}[]{|c|c||c|c|c|c|}\hline\cr
Red&1&(A0,C7)&(A1,C2)&(B0,D1)&(B1,D2)\\\
Black&2&(A0,C1)&(A1,C0)&(B0,B3)&(D0,D1)\\\
Blue&3&(A0,D6)&(A1,B4)&(B1,C6)&(C1,D3)\\\
Hazel&4&(A0,B3)&(A1,D7)&(B0,C5)&(C0,D2)\\\
Green&5&(A0,C6)&(A1,C7)&(B0,B5)&(D1,D2)\\\ \hline\cr\end{array}$ (19)

Figure 13: The egc Armanios-Wells $(12)^{5}$-graph and the non-egc Sylvester
$8^{4}$-graph.

where indices are taken$\pmod{8}$, so colored-edge orbits$\pmod{4}$ are either
of the form

$\begin{array}[]{l}\\{(X0,Yi),(X2,Y(i+2)),(X4,Y(i+4),(X6,Y(i+6))\\}\mbox{ or
of the form:}\\\ \\{(X1,Yj),(X3,Y(j+2)),(X5,Y(j+4),(X7,Y(j+6))\\}\end{array}$

with $X,Y\in\\{A,B,C,D\\}$, $i,j\in\mathbb{Z}_{8}$ and addition
taken$\pmod{8}$. The left of Fig. 13 contains the subgraph of ${\rm AW}$
spanned by the twelve 5-cycles through the black edge $(A0,C1)$ (where the two
dashed lines must be identified), showing the disposition of twelve 5-cycles
around an edge of ${\rm AW}$. Moreover, the four black edges in the second
line of (19) represent forty-eight tightly colored 5-cycles, (twelve passing
through each black edge, corresponding to the $\frac{5!}{2\times 5}=12$
existing color cycles

$\begin{array}[]{c}(23451),(23541),(24351),(24531),(25341),(25431),\\\
(24513),(25413),(25134),(24135),(23514),(25143))\end{array}$

, and each such cycle yields an orbit of four such 5-cycles. Since each edge
of ${\rm AW}$ passes through twelve 5-cycles of ${\rm AW}$ and $|E({\rm
AW})|=80$, we count $80\times 12$ 5-cycles in ${\rm AW}$ with repetitions.
Each 5-cycle in this count is repeated five times, so the number of 5-cycles
in ${\rm AW}$ is $(80\times 12)/5=16\times 12$. Thus, the number of orbits of
tightly-colored 5-cycles is 48 and we obtain a tight coloring of ${\rm AW}$.
(b) The upper right of Fig. 13 represents ${\rm Syl}$ with 5-cycles

$\begin{array}[]{lllll}C_{0}=(abcde)\\!&C_{1}=(aefgh)\\!&C_{2}=(abcgh)\\!&C_{3}=(cdefg)\\!&C_{4}=(bcdij)\;C_{5}=(hidea)\\\
C_{6}=(hijba)\\!&C_{7}=(cghid)\\!&C_{8}=(akmde)\\!&C_{9}=(ablne)\\!&C_{10}=(abcpo)\\\
C_{11}=(cderq)\\!&C_{12}=(aefso)\\!&C_{13}=(eahtr)\\!&C_{14}=(aksvo)\\!&C_{15}=(enutr).\end{array}$

The union of $C_{0},C_{1},C_{4},C_{8},C_{9}$ yields the red subgraph. Coloring
tightly $C_{0},C_{8},C_{9},C_{10},$

$C_{11}$ with color($ab$)=color($ef$) and color($ah$)=color($de$) makes
impossible continuing coloring tightly $C_{4}$, see below ${\rm Syl}$ in Fig.
13. Otherwise, to the right a forced tight coloring of $C_{0},\ldots,C_{12}$,
$C_{14}$ and $C_{15}$ is shown. That leaves $C_{13}$ obstructing a tight-
coloring. Thus, ${\rm Syl}$ is not egc. ∎

Subsequently, an egc $4^{3}0^{2}$-graph $\Gamma$ is presented by means of a
construction that generalizes the barrel constructions used in Section 5, as
follows. See the top of Fig. 14, where fourteen vertical copies of the
Petersen graph ${\rm Pet}$ are presented in parallel at equal distances from
left to right and numbered from 0 to 13 in $\mathbb{Z}_{14}$. The vertices of
the $j$-th copy ${\rm Pet}^{j}$ of ${\rm Pet}$ are denoted
$v_{1}^{j},v_{1}^{j},\ldots,v_{10}^{j}$ from top to bottom and are joined
horizontally by cycles of the Cayley graph of $\mathbb{Z}_{14}$ with generator
set $\\{1,3,5\\}$, namely the cycles

$\displaystyle\begin{array}[]{ll}(v_{i}^{0},v_{i}^{1},v_{i}^{2},v_{i}^{3},v_{i}^{4},v_{i}^{5},v_{i}^{6},v_{i}^{7},v_{i}^{8},v_{i}^{9},v_{i}^{10},v_{i}^{11},v_{i}^{12},v_{i}^{13}),&\mbox{
for }i=1,5,7,9;\\\
(v_{i}^{0},v_{i}^{3},v_{i}^{6},v_{i}^{9},v_{i}^{12},v_{i}^{1},v_{i}^{4},v_{i}^{7},v_{i}^{10},v_{i}^{13},v_{i}^{2},v_{i}^{5},v_{i}^{8},v_{i}^{11}),&\mbox{
for }i=2,3,4;\\\
(v_{i}^{0},v_{i}^{5},v_{i}^{10},v_{i}^{1},v_{i}^{6},v_{i}^{11},v_{i}^{2},v_{i}^{7},v_{i}^{12},v_{i}^{3},v_{i}^{8},v_{i}^{13},v_{i}^{4},v_{i}^{9}),&\mbox{
for }i=6,8,10.\\\ \end{array}$ (23)

######  Theorem 29.

There exists an egc $4^{3}0^{2}$-graph $\Gamma$ of order $140\times k$, for
every $0<k\in\mathbb{Z}$, representing all color-cycle permutations, $14k$
times each.

###### Proof.

We assert that an egc $4^{3}0^{2}$-graph as in the statement contains $14k$
disjoint copies of ${\rm Pet}$. We consider the case represented in the top of
Fig. 14 for $k=1$ and leave the details of the general case to the reader.
Notice the 6-cycle
$(v_{5}^{j},v_{6}^{j},v_{7}^{j},v_{8}^{j},v_{9}^{j},v_{10}^{j})$ in ${\rm
Pet}^{j}$, with its three pairs of opposite vertices
$\\{v_{5}^{j},v_{8}^{j}\\}$, $\\{v_{6}^{j},v_{9}^{j}\\}$,
$\\{v_{7}^{j},v_{10}^{j}\\}$ joined respectively to the neighbors
$v_{2}^{j},v_{3}^{j},v_{4}^{j}$ of the top vertex $v_{1}^{j}$, for
$j\in\mathbb{Z}_{14}$. A representation of the common proper coloring of the
graphs ${\rm Pet}^{j}$ is in the lower-left part of Fig. 14, where the
vertices $v_{i}^{j}$, for $i=1,\ldots,10$ and $j\in\mathbb{Z}_{14}$, are
simply denoted $i$. This figure shows the twelve 5-cycles of ${\rm Pet}$ as
color cycles, with red, black, blue, hazel and green taken respectively as 1,
2, 3, 4 and 5. This gives the one-to-one correspondence, call it $\eta$, from
the 5-cycles of ${\rm Pet}$ onto their color 5-cycles in the top part of Table
8.

Figure 14: Egc $4^{3}0^{2}$-graph on 140 vertices; Petersen and dodecahedral
graphs.

There are exactly twelve color 5-cycles; they are the targets $\eta$. They are
obtained from the 5!=120 permutations on five objects as the twelve orbits of
the dihedral group $D_{10}$ generated both by translations$\pmod{5}$ and by
reflections of the 5-tuples on $\\{1,2,3,4,5\\}$. The edges of $\Gamma$ not in
$\cup_{j=0}^{13}Pet^{j}$ occur between different copies ${\rm Pet}^{j}$ of
$Pet$; these are colored as shown in the bottom part of Table 8. This insures
the statement for $k=1$, since the twelve vertical copies ${\rm Pet}^{j}$ of
${\rm Pet}$ are the only source of the color cycles. The extension of this for
any $0<k\in\mathbb{Z}$ is immediate. ∎

The dodecahedral graph ${\rm Dod}$ with vertex set
$\\{u_{i},w_{i}|i=1,2,\ldots,10\\}$ and edge set formed by an edge pair
$\\{(u_{i},w_{i^{\prime}}),(u_{i^{\prime}},w_{i})\\}$ for each
$(v_{i},v_{i^{\prime}})\in(E({\rm
Pet})\setminus\\{(v_{5},v_{6}),(v_{7},v_{8}),(v_{9},v_{10})\\})$ and an edge
pair $\\{(u_{i},u_{i+1}),(w_{i},w_{i+1})\\}$ for each $i\in\\{5,7,9\\}$, is
represented in the lower-right of Fig. 14, where $u_{i}$ and $w_{i}$ (that we
will refer to as antipodal vertices) are respectively indicated by $i$ and
$i^{\prime}$, for $i=1,\ldots,10$. ${\rm Dod}$ is a 2-covering graph of ${\rm
Pet}$ via the graph map $\phi:{\rm Dod}\rightarrow{\rm Pet}$ such that
$\phi^{-1}(\\{v_{i}\\})=\\{u_{i},w_{i}\\}$.

$\begin{array}[]{|lll|llll|}\hline\cr(1,2,5,10,4)&\rightarrow&(1,2,3,4,5)&&(3,6,7,8,9)&\rightarrow&(4,1,3,5,2)\\\
(4,1,2,8,7)&\rightarrow&(5,1,4,3,2)&&(10,9,3,6,5)&\rightarrow&(1,2,4,5,3)\\\
(1,2,5,6,3)&\rightarrow&(1,2,5,4,3)&&(4,7,8,9,10)&\rightarrow&(2,3,5,1,4)\\\
(2,5,10,9,8)&\rightarrow&(2,3,1,5,4)&&(1,3,6,7,4)&\rightarrow&(3,4,1,2,5)\\\
(5,10,4,7,6)&\rightarrow&(3,4,2,1,5)&&(2,8,9,3,1)&\rightarrow&(4,5,2,3,1)\\\
(10,4,1,3,9)&\rightarrow&(4,5,3,2,1)&&(5,6,7,8,2)&\rightarrow&(5,1,3,4,2)\\\
\hline\cr\end{array}$

$\begin{array}[]{|ccc|}\hline\cr(v_{1}^{j},v_{1}^{j+1})\mbox{ has color
}2,\mbox{ if }j\equiv 0\pmod{2}&\mbox{and}&4,\mbox{ if }j\equiv 1\pmod{2}\\\
(v_{5}^{j},v_{5}^{j+1})\mbox{ has color }1,\mbox{ if }j\equiv
0\pmod{2}&\mbox{and}&3,\mbox{ if }j\equiv 1\pmod{2}\\\
(v_{7}^{j},v_{7}^{j+1})\mbox{ has color }5,\mbox{ if }j\equiv
0\pmod{2}&\mbox{and}&4,\mbox{ if }j\equiv 1\pmod{2}\\\
(v_{9}^{j},v_{9}^{j+1})\mbox{ has color }3,\mbox{ if }j\equiv
0\pmod{2}&\mbox{and}&4,\mbox{ if }j\equiv 1\pmod{2}\\\
(v_{2}^{j},v_{2}^{j+3})\mbox{ has color }5,\mbox{ if }j\equiv
0\pmod{2}&\mbox{and}&3,\mbox{ if }j\equiv 1\pmod{2}\\\
(v_{3}^{j},v_{3}^{j+3})\mbox{ has color }1,\mbox{ if }j\equiv
0\pmod{2}&\mbox{and}&5,\mbox{ if }j\equiv 1\pmod{2}\\\
(v_{4}^{j},v_{4}^{j+3})\mbox{ has color }1,\mbox{ if }j\equiv
0\pmod{2}&\mbox{and}&3,\mbox{ if }j\equiv 1\pmod{2}\\\
(v_{6}^{j},v_{6}^{j+5})\mbox{ has color }3,\mbox{ if }j\equiv
0\pmod{2}&\mbox{and}&2,\mbox{ if }j\equiv 1\pmod{2}\\\
(v_{8}^{j},v_{8}^{j+5})\mbox{ has color }1,\mbox{ if }j\equiv
0\pmod{2}&\mbox{and}&2,\mbox{ if }j\equiv 1\pmod{2}\\\
(v_{10}^{j},v_{10}^{j+5})\mbox{ has color }5,\mbox{ if }j\equiv
0\pmod{2}&\mbox{and}&2,\mbox{ if }j\equiv 1\pmod{2}\\\ \hline\cr\end{array}$

Table 8: Color assignment of the $4^{3}0^{2}$-graph $\Gamma$ in Theorem 29

.

######  Theorem 30.

There exists an egc $2^{3}0^{2}$-graph $\Gamma$ of order $140\times k$, for
every $0<k\in\mathbb{Z}$.

###### Proof.

We consider the case $k=1$ and leave the details of the general case to the
reader. We take seven vertical copies of ${\rm Dod}$ presented in parallel at
equal distances from left to right and numbered from 0 to 6 in
$\mathbb{Z}_{7}$. The vertices of the $j$-th copy ${\rm Dod}^{j}$ of ${\rm
Dod}$ are denoted $u_{1}^{j}$ and $w_{i}^{j}$, for $i=1,\ldots,10$ and are
joined by the additional cycles

$\displaystyle\begin{array}[]{ll}(u_{i}^{0},u_{i}^{1},u_{i}^{2},u_{i}^{3},u_{i}^{4},u_{i}^{5},u_{i}^{6},w_{i}^{0},w_{i}^{1},w_{i}^{2},w_{i}^{3},w_{i}^{4},w_{i}^{5},w_{i}^{6}),&\mbox{
for }i=1,5,7,9;\\\
(u_{i}^{0},u_{i}^{3},u_{i}^{6},u_{i}^{2},u_{i}^{5},u_{i}^{1},u_{i}^{4},w_{i}^{0},w_{i}^{3},w_{i}^{6},w_{i}^{2},w_{i}^{5},w_{i}^{1},w_{i}^{6}),&\mbox{
for }i=6,8,10;\\\
(u_{i}^{0},u_{i}^{5},u_{i}^{3},u_{i}^{1},u_{i}^{6},u_{i}^{4},u_{i}^{2},w_{i}^{0},w_{i}^{5},w_{i}^{3},w_{i}^{1},w_{i}^{6},w_{i}^{4},w_{i}^{2}),&\mbox{
for }i=2,3,4.\\\ \end{array}$ (27)

so that each such additional cycle passes through two antipodal vertices of
each copy ${\rm Dod}^{j}$. Notice the change of the order of the indices
$i\in\\{1,\ldots,10\\}$ in the assignment of the additional cycles in display
(27) with respect to the one in display (23). This is done to avoid the
formation of 5-cycles not entirely contained in the copies ${\rm Dod}^{j}$
($j\in\mathbb{Z}_{7}$). Since ${\rm Dod}$ has girth 5 and signature
$2^{3}=222$, the graph $\Gamma$ given by the union of the seven copies ${\rm
Dod}^{j}$ and the just presented additional cycles is a $2^{3}0^{2}$-graph. By
coloring the edges of the additional cycles of $\Gamma$ via the same color
pattern as in Theorem 29, it is seen that $\Gamma$ is egc. ∎

The truncated-icosahedral graph $TI$ is the graph of the truncated
icosahedron. This is obtained from the icosahedral graph, i.e. the line graph
${\rm Ico}=L({\rm Dod})$ of ${\rm Dod}$, by replacing each vertex $v$ of ${\rm
Ico}$ by a copy $C_{5}^{TI}(v)$ of its open neighborhood $N_{Ico}(v)$,
considering all such copies $C_{5}^{TI}(v)$ pairwise disjoint, and replacing
each edge $(u,v)$ of ${\rm Ico}$ by an edge from the vertex corresponding to
$u$ in $C_{5}^{TI}(v)$ to the vertex corresponding to $v$ in $C_{5}^{TI}(u)$.
Note $TI$ has sixty vertices, ninety edges, twelve 5-cycles, twenty 6-cycles
and signature $1^{2}0=110$.

######  Theorem 31.

There exists an egc $10^{4}$-graph on $840.k$ vertices, for each integer
$k>0$.

###### Proof.

By means of a barrel-type construction as in Fig. 14, one can combine $14k$
copies of $TI$ and the Cayley graph of $\mathbb{Z}_{14}$ with generator set
$\\{1,3,5\\}$ to get an egc graph as claimed. ∎

######  Remark 32.

The point graph of the generalized hexagon $GH(1,5)$ [2, p. 204], the point
graph of the Van Lint–Schrijver partial geometry [2, p. 307] and the odd graph
[2, p. 259] on eleven points are distance-regular with intersection arrays
$\\{6,5,5;1,1,6\\}$, $\\{6,5,5,4;1,1,2,6\\}$ and $\\{6,5,5,4,4;1,1,2,2,3\\}$,
respectively. If their chromatic number were 6, they would be $(125)^{6}$-,
$(25)^{6}$\- and $(25)^{6}$-graphs, respectively, but it is known that none of
them is egc.

##  7 Hamilton cycles and hamiltonian decomposability

Some feasible applications of egc graphs occur when the unions of pairs of
composing 1-factors are Hamilton cycles, possibly attaining hamiltonian
decomposability in the even-degree case. This offers a potential benefit to
the applications drawn in Section 1, if an optimization/decision-making
problem requires alternate inspections covering all nodes of the involved
system, when the alternacy of two colors is required.

In Fig. 1, the cases (h–j) and their triangle-replaced graphs (m-o) as well as
the case (u), and the 3-colored dodecahedral graph ${\rm Dod}$ that has the
case (u) as its triangle replaced graph, have the unions of any two of their
1-factors forming a Hamilton cycle, while the cases (k), (p) and (v) have
those unions as disjoint pairs of two cycles of equal length. In particular,
the 3-cube graph $Q_{3}$ that admits just two tight factorizations, has one of
them creating Hamilton cycle (case (l) via green and either red or blue edges,
but not red and blue edges). The triangle-replaced graph, $\nabla(Q_{3})$, has
corresponding tight factorizations in cases (p–q) with similar differing
properties as those of cases (k–l). Preceding Theorem 4, similar comments are
made for $\nabla(\Gamma^{\prime})$, where $\Gamma^{\prime}$ is ${\rm Dod}$ or
the Coxeter graph ${\rm Cox}$. Recall the union of two 1-factors of ${\rm
Dod}$ is hamiltonian while the union of two 1-factors of ${\rm Cox}$ is not.

$\begin{array}[]{||c||c|c|c|c|c|c||c||c|c|c||c||c|c|c||}\hline\cr
s=1&5&7&9&11&13&15&s=3&5&7&9&s=5&5&7&9\\\
\hline\cr\\!r=6&113&&&&&&\\!r=6&131&&&&&&\\\
\\!r=8&211&114&&&&&\\!r=8&114&211&&&&&\\\
\\!r=10&111&111&511&&&&\\!r=10&111&511&111&\\!r=10&555&151&151\\\
\\!r=12&213&312&112&116&&&\\!r=12&132&233&336&\\!r=12&611&611&211\\\
\\!r=14&111&111&111&111&117&&\\!r=14&141&111&111&\\!r=14&711&111&117\\\
\\!r=16&211&114&114&112&211&118&\\!r=16&411&112&112&\\!r=16&811&211&211\\\
\\!r=18&113&311&111&311&311&111&\\!r=18&131&131&333&\\!r=18&911&111&111\\\
\\!r=20&211&112&215&215&112&112&\\!r=20&211&512&112&\\!r=20&a51&251&251\\\
\\!r=22&111&111&111&111&111&111&\\!r=22&111&111&111&\\!r=22&b11&111&111\\\
\\!r=24&213&314&411&611&611&114&\\!r=24&133&231&336&\\!r=24&c11&211&211\\\
\\!r=26&111&111&111&111&111&111&\\!r=26&111&111&111&\\!r=26&d11&111&111\\\
\\!r=28&211&112&211&211&217&711&\\!r=28&112&211&112&\\!r=28&e11&211&217\\\
\\!r=30&113&311&115&115&111&111&\\!r=30&132&135&333&\\!r=30&f11&151&111\\\
\hline\cr\end{array}$ Table 9: Various cases of Theorem 10 item 3($e$).

In Fig. 2(d), the three color partitions of $Q_{4}$, namely (12)(34), (13)(24)
and (14)(23), yield 2-factorizations with 2-factors formed each by two cycles
of equal length $\frac{1}{2}|V(Q_{4})|=8$. We denote this facts by writing
$Q_{4}(2,2,2)$. In a likewise fashion, we can denote toroidal items in Fig. 2
as follows: (e) $\\{4,4\\}_{12,2}^{4}(1,4,3)$, formed by 2-factorizations with
2-factors of one, three and four cycles of equal lengths 24, 6 and 8,
respectively. Similarly: (f) $\\{4,4\\}_{10,2}^{4}(1,2,1)$; (g)
$\\{4,4\\}_{6,3}^{3}(3,3,3)$; (h) $\\{4,4\\}_{20,1}^{0}(2,1,1)$; (i)
$\\{4,4\\}_{28,1}^{0}(1,1,2)$; and (j) $\\{4,4\\}_{22,1}^{5}(1,2,1)$.

Table 9 lists various cases of Theorem 10 item 3($e$), indicating without
parentheses or commas the triples $abc$ corresponding to the numbers $a$, $b$
and $c$ of cycles (of equal length in each case) of the respective 2-factors
$(12)$, $(13)$ and $(14)$.

######  Remark 33.

For the toroidal cases in Theorem 10 item 3 depicted as in Fig. 2(f,g,h,j),
assume that the 2-factors $(12)$ and $(14)$ complete 2-factorizations composed
by 1-zigzagging cycles of equal length (i.e., composed by alternating
horizontal and vertical edges) and that the 2-factors $(13)$ and $(24)$ are
composed by vertical and horizontal edges, respectively. This way, while
vertical edges form $\gcd(r,s)$ cycles of equal length, horizontal edges form
$t$ cycles of not necessarily the same length, so the notation in the previous
paragraph cannot be carried out for example for item 3($e$) because
$\gcd(r,s)\neq t$. So we modify that notation for such cases by simply writing
$\\{4,4\\}_{r,t}^{s}(a,b,c)$, that we call the star notation [9].

######  Theorem 34.

In the star notation of Remark 33, each applicable toroidal case
$\Gamma=\\{4,4\\}_{r,t}^{s}$ as in Theorem 10 is expressible as:
$\\{4,4\\}_{r,t}^{s}(\frac{1}{2}\gcd(r,|t-s|),\gcd(r,s),\frac{1}{2}\gcd(r,t+s)).$

###### Proof.

We prove the statement for the toroidal cases of Theorem 10 with two colors on
horizontal cycles and the other two on vertical cycles, for the factorization
$\\{F_{12},F_{34}\\}$, and leave the rest to the reader. Consider the straight
upper-right-to-lower-left line $L_{1}$ from the upper-right vertex $(0,0)$ in
the cutout $\Phi$ (Remark 5) of $\mathbb{Z}_{r}\times\mathbb{Z}_{t}$ passing
through $(0,r-t+s)$ in the lower border of $\Phi$ and formed by the diagonals
of $\frac{rt}{2\gcd(r,|t-s|)}$ squares representing 4-cycles of $\Gamma$.
$L_{1}$ determines two 1-zigzagging cycles $C_{1}^{0},C_{1}^{1}$ through
$(0,0)$ in $F_{12},F_{34}$, respectively, touching $L_{1}$ on alternate
vertices of $\Gamma$. In the end, we get parallel lines $L_{1},\ldots,L_{z}$,
where $z=\frac{1}{2}\gcd(r,|t-s|)$ such that each $L_{i}$ ($i=1,\ldots,z$)
determines two 1-zigzagging cycles $C_{i}^{0},C_{i}^{1}$ in $F_{12},F_{34}$,
respectively, touching $L_{i}$ at alternate vertices of $\Gamma$. An example
is shown in Fig. 2(c) for $r=12,t=5,s=9$ with $z=2$, where $L_{1}$ is given in
black thin trace and $L_{2}$ is given in gray thin trace, (not considering
here the intermittent diagonals). ∎

######  Corollary 35.

If $\frac{1}{2}\gcd(r,|t-s|)=\gcd(r,s)=\frac{1}{2}\gcd(r,t+s)=1$, then the
2-factors $(12)$, $(34)$, $(13)$, $(14)$ and $(23)$ are composed by a Hamilton
cycle each (a total of six Hamilton cycles), comprising the 2-factorizations
$(12)(34)$ and $(14)(23)$.

###### Proof.

This is due to Remark 33 and to the quadruple equality in the statement. ∎

Additional examples are provided in display (32) for fixed $t=2$, as in
Theorem 10 item 3($b$). The reader is invited to do similarly for Theorem 10,
items 3($a$) and 3($c$).

$\displaystyle\begin{array}[]{||c||c|c||c||c|c||c||c|c||c||}\hline\cr
r&s=4&s=6&r&s=4&s=6&r&s=4&s=6\\\ \hline\cr 8&141&&14&121&121&20&141&122\\\
10&121&&16&141&124&22&121&121\\\ 12&143&162&18&123&131&24&143&164\\\
\hline\cr\end{array}$ (32)

The toroidal graphs in Theorem 10 items 1($c$) and 2($b$) behave differently
from those in Theorem 34 in that the 2-factors in question are 1-zigzagging in
only one of the three 2-factorizations, while the other two 1-factorizations
are 2-zigzagging, namely:

  1. (a)

in Theorem 10 items 1($c$) and 2($b$), just for $s\equiv 1\pmod{4}$, the
1-factorization (12)(34) is 1-zigzagging and the 1-factorizations (13)(24) and
(14)(23) are 2-zigzagging;

  2. (b)

in Theorem 10 item 2($b$) just for $s\equiv 3\pmod{4}$, the 2-factorizations
(12)(34)–(13)(24) are 2-zigzagging and the 2-factorization (14)(23) is
1-zigzagging.

Figure 15: Two egc edge-colored 4-cube graphs.

######  Corollary 36.

In all cases of Theorem 10 item 2(b), there are exactly two hamiltonian
2-factorizations. Moreover, the toroidal graphs $\Gamma$ in Theorem 10 are

  1. 1.

$\Gamma(222)$, for items 1(c)–2(a);

  2. 2.

$\Gamma(211)$, for item 2(b) just for $s\equiv 1\pmod{4}$;

  3. 3.

$\Gamma(112)$, for item 2(b) just for $s\equiv 3\pmod{4}$.

###### Proof.

The previous comments cover the points in the statement.∎

##  8 Applications to 3-dimensional geometry

Fig. 15 redraws the two toroidal copies of $Q_{4}$ in the lower center–right
of Fig. 3, (which arise respectively in Subsection 3.1 from the central–right
latin squares in display (6)), as edge-colored tesseracts, in order to extract
piecewise linear (PL) [20] realizations of two enantiomorphic compounds of
four Möbius strips each [11, 12]. In the sequel, this results to be equivalent
to corresponding enantiomorphic Holden-Odom-Coxeter polylinks of four locked
hollow equilateral triangles each [6, 13, 14], from a group-theoretical point
of view .

###  8.1 Usage of the two nontrivial Latin squares in MOLS(4)

Figure 16: Assignment of pairs of colors to the edges of 3-cubes

Fig. 17 contains two horizontal sets of four copies of $Q_{3}$ each. A 6-cycle
$\xi_{i}$ is distinguished in each such copy $Q_{3}^{i}$ of $Q_{3}$ with a
respective color $i$ ($i=1$ for red, $i=2$ for blue, $i=3$ for green and $i=4$
for hazel). Each $Q_{3}^{i}$ has its $\xi_{i}$ with the edges marked
$x_{i}^{j}$, where $x=t$ for a trapezoid and $x=p$ for a parallelogram
(quadrangles that are the faces of PL Möbius strips as in Fig. 19),
$i\in\\{1,2,3,4\\}$ for associated color and $j\in\\{h,v,d\\}$ for edge
direction ($h$ for horizontal, $v$ for vertical and $d$ for in-depth). The top
(resp. bottom) set has each $Q_{3}^{i}$ with a one-to-one correspondence from
its edges $t_{i}^{j}$ ($p_{i}^{j}$) to the edges with color $i$ and direction
$j$ in the inner (outer) copy of $Q_{3}$ in the left (resp. right) copy of
$Q_{4}$ in Fig. 15. This way, each $Q_{3}^{i}\setminus\xi_{i}$ in Fig. 17 is
formed by two antipodal vertices that are joined by a color-$i$ dashed axis,
allowing to visualize $120^{\circ}$ angle rotations representing color-
and-($t$-or-$p$)-preserving automorphisms that will reappear in relation to
Fig. 18-19.

The two leftmost 3-cubes in Fig. 16 have each of their edges assigned a pair
of colors in $\\{1,2,3,4\\}$. The first (resp. second) color is obtained from
the corresponding row of 3-cubes in Fig. 17 as the color $i$ of the only edge
$t_{i}^{j}$ (resp. $p_{i}^{j}$) in that edge position among the four cases in
the row. This allows an assignment of a color to each face quadrant of the
cube, as shown on the center and right in Fig. 16, and figuring the twenty-
four such quadrants in each of the two cases. Note that the faces in these
cubes are given an orientation each. The color pairs in Fig. 17 can be
recovered from the quadrant colors in Fig. 16 by reading them along an edge
according to the corresponding face orientation.

###  8.2 Compound of four PL Möbius strips

Fig. 18 depicts the union $[0,3]^{3}\subset\mathbb{R}^{3}$ of twenty-seven
unit 3-cubes. In it, information carried by the top rows in Fig. 17 determines
four PL trefoil knots, one per each color $i\in\\{1,2,3,4\\}$. These trefoil
knots are indicated in thick trace along edges of the said unit cubes. These
$i$-colored thick-traced edges determine two parallel sides of either a
trapezoid or a parallelogram, as illustrated in Fig. 19, for $i=4=$ hazel
color. In the case of a trapezoid (resp. parallelogram), the lengths of those
sides are 3 internally and 1 externally (resp. 2 internally and 2 externally).
The other two sides of each trapezoid or parallelogram are presented in thin
trace in the color $i$ to distinguish them from the thick trace of the trefoil
knot sides. Note that the constructed trapezoids and parallelograms determine
four PL Möbius strips that give place to the following results. (Similar
results for the bottom half of Fig. 17 are omitted and left for the interested
reader to figure out).

Figure 17: Edges of rotation.

######  Theorem 37.

There exists a maximum-area PL Möbius strip $M_{1}$ embedded in
$[0,3]^{3}\setminus[1,2]^{3}\subset\mathbb{R}^{3}$ whose boundary is a PL
closed curve $C_{1}$ formed by a minimum of segments parallel to the
coordinate directions and whose end-vertices are points in $\mathbb{Z}^{3}$.

###### Proof.

A strip as in the statement is represented in Fig. 19 (whose PL boundary is
also present in Fig. 18 as the hazel trefoil knot), with the mentioned
segments as in the following display (where, starting clockwise at the left
upper corner of Fig. 19, colors of quadrilaterals are cited and, between
parentheses, whether they are shown full or in part):

$\displaystyle\begin{array}[]{|cc|c|c|c|c|c|}&gray(part)&green(part)&yellow(full)&gray(part)&green(full)&yellow(part)\\\
\hline\cr&[103,203]_{1}^{h}&[203,201]_{2}^{v}&[201,231]_{3}^{d}&[231,031]_{2}^{h}&[031,032]_{1}^{v}&[032,012]_{2}^{d}\\\
&[012,312]_{3}^{h}&[312,310]_{2}^{v}&[310,320]_{1}^{d}&[320,120]_{2}^{h}&[120,123]_{3}^{v}&[123,103]_{2}^{d}\\\
\hline\cr\end{array}$ (36)

Here, a segment denoted $[a_{1}a_{2}a_{3},b_{1}b_{2}b_{3}]$ stands for
$[(a_{1},a_{2},a_{3}),(b_{1},b_{2},b_{3})]$, with
$a_{i},b_{i}\in\\{0,1,2,3\\}$, ($i=1,2,3$). In (1), each of the twelve
segments are appended with its length as a subindex and an element of
$\\{h,v,d\\}$ as a superindex, where $h,v,$ and $d$ stand for horizontal,
vertical and in-depth directions, respectively. The PL curve $C_{4}$, a PL
trefoil knot, is depicted in thick hazel trace in Fig. 18 (via unbroken unit-
segment edges). ∎

######  Theorem 38.

The maximum number of Möbius strips in $[0,3]^{3}\setminus[1,2]^{3}$ as in
Theorem 37 and whose boundaries have pairwise intersections of dimension 0
(i.e., isolated points) is 4.

###### Proof.

To prove the statement, consider Fig. 18, where $C_{1}$ is again drawn, as
well as the blue PL trefoil $C_{2}$, defined by the segments:

$\displaystyle\begin{array}[]{ccccccc}&[100,200]_{1}^{h}&[200,220]_{v}^{2}&[220,223]_{3}^{d}&[223,023]_{2}^{h}&[023,013]_{1}^{v}&[013,011]_{2}^{d}\\\
&[011,311]_{3}^{h}&[311,331]_{v}^{2}&[331,332]_{1}^{d}&[332,331]_{2}^{h}&[331,102]_{3}^{v}&[102,100]_{2}^{d}\\\
\end{array}$ (39)

and the green PL trefoil $C_{3}$, defined by the segments:

$\displaystyle\begin{array}[]{ccccccc}&[133,233]_{1}^{h}&[233,213]_{2}^{v}&[213,210]_{3}^{d}&[210,010]_{2}^{h}&[010,020]_{1}^{v}&[020,022]_{2}^{d}\\\
&[022,322]_{3}^{h}&[322,302]_{2}^{v}&[302,301]_{1}^{d}&[301,101]_{2}^{h}&[101,131]_{3}^{v}&[131,133]_{2}^{d}\\\
\end{array}$ (42)

and the brown PL trefoil $C_{4}$, defined by the segments:

$\displaystyle\begin{array}[]{ccccccc}&[230,130]_{1}^{h}&[130,110]_{2}^{v}&[110,113]_{3}^{d}&[113,313]_{2}^{h}&[313,323]_{1}^{v}&[323,321]_{2}^{d}\\\
&[321,021]_{3}^{h}&[021,001]_{2}^{v}&[001,002]_{1}^{d}&[002,202]_{2}^{h}&[202,232]_{3}^{v}&[232,230]_{2}^{d}\\\
\end{array}$ (45)

Observe that the six (maximum) planar faces of $M_{1}$ intersect $C_{4}$ in
six pairs of segments, shown in display (36) vertically: first
$[103,203]_{1}^{h}$ above and $[012,312]_{3}^{h}$ below, which form an
isosceles trapezoid together with the segments $[103,012]$ and $[203,312]$;
then, $[203,201]_{2}^{v}$

above, and $[312,310]_{2}^{v}$ below, which form a parallelogram together with
the segments $[203,312]$ and $[201,310]$, etc. Similar observations can be
made with respect to displays (39)–(45). We denote such planar faces in (3-6)
by $t_{i}^{h},p_{i}^{d},t_{i}^{v},p_{i}^{h},t_{i}^{d},p_{i}^{v}$,
($i\in\\{1,2,3,4\\}$), as on the rightmost (color 4 =) hazel 3-cube in the
schematic Fig. 17.

Figure 18: PL Möbius strip whose PL boundary has color 4 = hazel.

Let us denote the maximum PL Möbius strips expanded by the PL trefoil knots
$C_{2}$, $C_{3}$ and $C_{4}$ respectively as $M_{2}$, $M_{3}$ and $M_{4}$. Let
us look at the segmental intersections of trapezoids and parallelograms in
$M=M_{1}\cup M_{2}\cup M_{3}\cup M_{4}$ from displays (6)–(39) above . Recall:
color 1 is red, color 2 is blue, color 3 is green and color 4 is brown.

The top-front set $TF_{i}^{h}=([000,300]\times[000,010]\times[000,001])\cap
M_{i}$ in $[0,3]^{3}$ is trapezoid $t_{2}^{h}$ for $i=2$ and parallelogram
$p_{3}^{h}$ for $i=3$. In the upper leftmost cube in Fig. 16, let us call it
$Q$, we indicate this segmental intersection by the edge-labelling pair 23,
with 2 in blue and 3 in green, which are the colors used to represent $C_{2}$
and $C_{3}$, respectively. This pair 23 labels the top-front horizontal edge
in $Q$, corresponding to the position of $TF_{2}^{h}\cap TF_{3}^{h}$ in Fig.
18.

In all edge-labelling pairs in $Q$ (Fig. 16), the first number is associated
to a trapezoid and the second one to a parallelogram, each number printed in
its associated color.

We subdivide the six faces of $Q$ into four quarters each and label them 1 to
4, setting external counterclockwise (or internal clockwise) orientations to
the faces, so that the two quarter numbers corresponding to an edge of any
given face yield, via the defined orientation, the labelling pair as defined
in the previous paragraph. This is represented in the center and rightmost
cubes in Fig. 16.

Figure 19: Four edge-disjoint PL trefoil subgraphs bounding four PL Möbius
strips.

We can identify the cube $Q$ with the union of the pairwise distinct
intersections $M_{i}\cap M_{j}$, ($1\leq i<j\leq 4$). This way, $Q$ becomes
formed by the segments:

$\displaystyle\begin{array}[]{cc}&{}^{[(0.5,0.5,0.5),(2.5,0.5,0.5)]_{2}^{3},[(0.5,2.5,0.5),(2.5,2.5,0.5)]_{1}^{4},[(0.5,0.5,2.5),(2.5,0.5,2.5)]_{3}^{2},[(0.5,2.5,2.5),(2.5,2.5,2.5)]_{4}^{1},}\\\
&{}^{[(0.5,0.5,0.5),(0.5,2.5,0.5)]_{3}^{4},[(2.5,0.5,0.5),(2.5,2.5,0.5)]_{1}^{2},[(0.5,0.5,2.5),(0.5,2.5,2.5)]_{4}^{3},[(2.5,0.5,2.5),(2.5,2.5,2.5)]_{2}^{1},}\\\
&{}^{[(0.5,0.5,0.5),(0.5,0.5,2.5)]_{4}^{2},[(2.5,0.5,0.5),(2.5,0.5,2.5)]_{1}^{3},[(0.5,2.5,0.5),(0.5,2.5,2.5)]_{2}^{4},[(2.5,2.5,0.5),(2.5,2.5,2.5)]_{3}^{1},}\end{array}$
(49)

where each segment is suffixed with its trapezoid color number as a subindex
and its parallelogram color number as a superindex. The first to third lines
in (42) display those segments of $Q$ parallel to the first to third
coordinates, respectively. Fig. 17 represents the Möbius strips $M_{i}$ in
$Q$, for $i=1,2,3,4$, with the $i$-colored edges corresponding to the
trapezoids and parallelograms of each $M_{i}$ labeled via $x_{i}^{j}$, ($x=t$
for trapezoid; $x=p$ for parallelogram; $j\in\\{h,v,d\\}$ for horizontal,
vertical and in-depth edges of $Q$, respectively). ∎

######  Theorem 39.

The automorphism group $G=Aut(\bigcup_{i=1}^{4}M_{i})$ of
$\bigcup_{i=1}^{4}M_{i}$ is isomorphic to
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. Moreover, there are
only two 4-PL-Möbius-strip compounds, one of which ($M_{4}$) is the one with
PL Möbius strip boundaries depicted as the PL trefoils in Fig. 18.
Furthermore, these two compounds are enantiomorphic.

Figure 20: Odom-Coxeter polylink.

###### Proof.

By way of the reflection $F_{O}$ of $[0,3]^{3}\setminus[1,2]^{3}$ about the
central vertex $O=(1.5,1.5,1.5)$ of $[0,3]^{3}$, each $M_{i}$ is transformed
bijectively and homeomorphically into $M_{5-i}$, for $i=1,2,3,4$. The
$180^{\circ}$ angle rotations $R_{d}^{2},R_{v}^{2},R_{h}^{2}$ of $[0,3]^{3}$
about the in-depth axis $x_{1}=x_{2}=1.5$, the vertical axis $x_{1}=x_{3}=1.5$
and the horizontal axis $x_{2}=x_{3}=1.5$, respectively, form the following
respective transpositions on the vertices of $[0,3]^{3}$:

$\displaystyle\begin{array}[]{llll}((x_{1},x_{2},x_{3}),(3-x_{1},&3-x_{2},&x_{3}&)),\forall
x_{i}\in\\{0,3\\},(i=1,2,3)\\\
((x_{1},x_{2},x_{3}),(3-x_{1},&x_{2},&3-x_{3}&)),\forall
x_{i}\in\\{0,3\\},(i=1,2,3)\mbox{ and}\\\
((x_{1},x_{2},x_{3}),(x_{1},&3-x_{2},&3-x_{3}&)),\forall
x_{i}\in\\{0,3\\},(i=1,2,3)\end{array}$ (53)

and determine the following permutations of Möbius strips $M_{i}$,
($i=1,2,3,4$):

$\displaystyle(M_{1},M_{3})(M_{2},M_{4}),\;(M_{1},M_{2})(M_{3},M_{4})\mbox{
and }(M_{1},M_{4})(M_{2},M_{3}).$ (54)

On the other hand, neither the reflections on the coordinate planes at
$O=(1.5,1.5,1.5)$ nor the $\pm 90^{\circ}$ angle rotations
$R_{d},R_{d}^{3},R_{v},R_{v}^{3},R_{h},R_{h}^{3}$ preserve the union
$\bigcup_{i=1}^{4}M_{i}$ but yield a 4-PL-Möbius-strip compound that is
enantiomorphic to $\bigcup_{i=1}^{4}M_{i}$. Moreover, $G$ is generated by
$F_{O}$, $R_{d}$, $R_{v}$ and $R_{h}$. ∎

###  8.3 Polylink of four hollow triangles

A sculpture by G. P. Odom Jr., see Fig. 20, was analyzed by H. S. M. Coxeter
[6], for its geometric and symmetric properties. According to [21, p. 270],
Odom and Coxeter were unaware of the earlier discovery [13] of this by A.
Holden, who called it a regular polylink of four locked hollow triangles [14].

We relate the top Möbius-strip compound above to this structure, noting that
the centers of the maximum linear parts of the PL trefoil knots $C_{i}$
($i=1,2,3,4$) are the vertices of four corresponding equilateral triangles,
namely (in the order of the triangle colors):

$\displaystyle\begin{array}[]{cccc|cccc}1&(1.5,0,3),&(3,1.5,0),&(0,3,1.5);&2:&(1.5,0,0),&(0,1.5,3),&(3,3,1.5);\\\
3:&(1.5,3,3),&(0,1.5,0),&(3,0,1.5);&4:&(1.5,3,0),&(3,1.5,3),&(0,0,1.5).\end{array}$
(57)

Each of these triangles $T_{i}$ ($i=1,2,3,4$), gives place to a hollow
triangle (i.e., a planar region bounded by two homothetic and concentric
equilateral triangles [6]) by removing from $T_{i}$ the equilateral triangle
$T^{\prime}_{i}$ whose vertices are the midpoints of the segments between the
vertices of $T_{i}$ (display (57)) and $O=(1.5,1.5,1.5)$. Characterized by
colors, these midpoints are

$\displaystyle\begin{array}[]{cccc}1:&(1.50,0.75,2.25),&(2,25,1.50,0.75),&(0.75,2.25,1.50);\\\
2:&(1.50,0.75,0.75),&(0.75,1.50,2.25),&(2.25,2.25,1.50);\\\
3:&(1.50,2.25,2.25),&(0.75,1.50,0.75),&(2.25,0.75,1.50);\\\
4:&(1.50,2.25,0.75),&(2.25,1.50,2.25),&(0.75,0.75,1.50).\end{array}$ (62)

The centers in display (57) are the vertices of an Archimedean cuboctahedron.
Consider the midpoints of the sides of the triangles $T_{i}$, namely:

$\displaystyle\begin{array}[]{cccc}1:&(2.25,0.75,1.50),&(1.50,2.25,0.75),&(0.75,1.50,2.25);\\\
2:&(0.75,0.75,1.50),&(1.50,2.25,2.25),&(2.25,1.50,0.75);\\\
3:&(0.75,2.25,1.50),&(1.50,0.75,0.75),&(2.25,1.50,2.25);\\\
4:&(2.25,2.25,1.50),&(1.50,0.75,2.25);&(0.75,1.50,0.75).\end{array}$ (67)

By expressing the 3-tuples in (62) via a $4\times 3$-matrix
$\\{A_{i,j};i=1,2,3;j=1,2,3,4\\}$, we have the following correspondence from
(62) to (67), in terms of the notation in Fig. 20:

$\displaystyle\begin{pmatrix}A_{1,1}&A_{1,2}&A_{1,3}\\\
A_{2,1}&A_{2,2}&A_{2,3}\\\ A_{3,1}&A_{3,2}&A_{3,3}\\\
A_{4,1}&A_{4,2}&A_{4,3}\end{pmatrix}\rightarrow\begin{pmatrix}B_{1,12}&B_{1,23}&B_{1,31}\\\
B_{2,12}&B_{2,23}&B_{2,31}\\\ B_{3,12}&B_{3,23}&B_{3,31}\\\
B_{4,12}&B_{4,23}&B_{4,31}\end{pmatrix}=\begin{pmatrix}A_{3,3}&A_{4,1}&A_{2,2}\\\
A_{4,3}&A_{3,1}&A_{1,2}\\\ A_{1,3}&A_{2,1}&A_{4,2}\\\
A_{2,3}&A_{1,1}&A_{3,2}\end{pmatrix}$ (68)

meaning each midpoint $B_{i,jk}$ of a $T_{i}$ between $B_{i,j}$ and $B_{i,k}$
equals a vertex $A_{i^{\prime},j^{\prime}}$ of some $T^{\prime}_{i^{\prime}}$,
and vice-versa, as in Fig. 20. Take each $T_{i}$ as the 6-cycle of its
vertices and side midpoints:

$\displaystyle\begin{array}[]{ccccccc}T_{1}=&(B_{1,1}&A_{3,3}&B_{1,2}&A_{4,1}&B_{1,3}&A_{2,2});\\\
T_{2}=&(B_{2,1}&A_{1,2}&B_{2,3}&A_{3,1}&B_{2,2}&A_{4,1});\\\
T_{3}=&(B_{3,1}&A_{1,3}&B_{3,2}&A_{2,1}&B_{3,3}&A_{4,2});\\\
T_{4}=&(B_{4,1}&A_{1,1}&B_{4,2}&A_{2,3}&B_{4,1}&A_{3,2}).\end{array}$ (73)

######  Corollary 40.

The automorphism group of the union $\bigcup_{i=1}^{4}T_{i}$ is
$G=Aut(\bigcup_{i=1}^{4}M_{i})=Aut(\bigcup_{i=1}^{4}T_{i})$. In addition,
$G_{i}=Aut(M_{i})=Aut(T_{i})$, for each $i=1,2,3,4$, is isomorphic to the
dihedral group of six elements. Moreover, there are only two polylinks of four
hollow triangles in $[0,3]^{3}$, including $\bigcup_{i=1}^{4}T_{i}$, and these
two polylinks are enantiomorphic.

###### Proof.

By expressing, as in Fig. 20, the vertices of $[0,3]^{3}$ by:

$\displaystyle\begin{array}[]{cccccccc}\mathbf{0}=000,&\mathbf{1}=300,&\mathbf{2}=030,&\mathbf{3}=330,\mathbf{4}=003,&\mathbf{5}=303,&\mathbf{6}=033,&\mathbf{7}=033,\end{array}$
(75)

we notice that the $\pm 120^{\circ}$ angle rotations of $[0,3]^{3}$ around the
axis line determined by the two points of color $i$ in $Q$, as indicated in
Fig. 17, correspond respectively to the permutations:

$\displaystyle\begin{array}[]{clll}Color\;1:&R_{1}=(\mathbf{124})(\mathbf{365})&\mbox{
and }&R_{1}^{-1}=(\mathbf{142})(\mathbf{563});\\\
Color\;2:&R_{2}=(\mathbf{036})(\mathbf{174})&\mbox{ and
}&R_{2}^{-1}=(\mathbf{063})(\mathbf{147});\\\
Color\;3:&R_{3}=(\mathbf{065})(\mathbf{271)}&\mbox{ and
}&R_{3}^{-1}=(\mathbf{056})(\mathbf{217});\\\
Color\>4:&R_{4}=(\mathbf{247})(\mathbf{053})&\mbox{ and
}&R_{4}^{-1}=(\mathbf{274})(\mathbf{035}),\end{array}$ (80)

where color 1 is red, color 2 is blue, color 3 is green and color 4 is hazel;
notice also that the axes in $Q$ corresponding to these colors are:

$\begin{array}[]{ccc}&[(0.5,0.5,0.5),(2.5,2.5,2.5)],&[(0.5,2.5,0.5),(2.5,0.5,2.5)],\\\
&[(0.5,0.5,2.5),(2.5,2.5,0.5)],&[(2.5,0.5,0.5),(0.5,2.5,2.5)].\end{array}$

The rest of the statement arises from Theorem 39. The fact that there are two
polylinks of four hollow triangles in $[0,3]^{3}$ that are enantiomorphic is
inherited from Theorem 39. ∎

## References

  * [1] C. Armanios, A new 5–valent distance transitive graph, Ars Combin. 19A (1985), 77–85.
  * [2] A. Brouwer, A, Neumaier, A. Cohen, Distance-Regular Graphs, Springer-Verlag, 1998.
  * [3] C. J. Colbourn, J. H. Dinitz, Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, (2007).
  * [4] J. H. Conway, N. J. A. Sloane, Sphere Packings, Lattices and Groups, (3rd ed.), Berlin, New York: Springer-Verlag, (1999).
  * [5] S. L. R. Costa, R. Muniz, E. Agustini, R. Palazzo, Graphs, Tessellations and Perfect Codes in Flat Tori, IEEE Transctions on Information Theory, 50-10(2004), 2363-2377.
  * [6] H. S. M. Coxeter, Symmetrical Combinations of Three or Four Hollow Triangles, The Mathematical Intelligencer, 16(3) (1994), 25–30.
  * [7] H. S. M. Coxeter, Self-Dual Configurations and Regular Graphs, Bull. Amer. Math. Soc. 56 (1950), 413–455.
  * [8] P. R. Cromwell, Polyhedra, Cambridge Univ. Press, Cambridge UK (1997).
  * [9] I. J. Dejter, O. Serra, Efficient dominating sets in Cayley graphs, Discrete Applied Mathematics 129(2–3) (2002), 319–328.
  * [10] E. Eiben, R. Jajcay, P. ’Šparl, Symmetry properties of generalized graph truncations, J. Combin. Theory, Ser. B 137 (2019) 29–131.
  * [11] D. Fuchs, S. Tabachnikov, Mathematical Omnibus: Thirty Lectures on Classic Mathematics, 2007, 199–206, at http://www.math.psu.edu/tabachni/Books/taba.pdf
  * [12] D. Hilbert, S. Cohn-Vossen, Geometry and the Imagination (2nd ed.), Chelsea, 1952.
  * [13] A. Holden, Shapes, Spaces and Symmetry, Columbia Univ. Press, 1971.
  * [14] A. Holden, Regular Polylinks, Structural Topology, 4 (1980), 41–45.
  * [15] W. Imrich, S. Klavžar, D. F. Rall, Graphs and their cartesian products, A. K. Peters, (2008).
  * [16] P. Potočnik, P. Spiga, G. Verret, A census of cubic vertex-transitive graphs https://staff.matapp.unimib.it/~spiga/census.html.
  * [17] P. Potočnik, J. Vidali, Girth-regular graphs, Ars Mathematica Contemporanea, 17 (2019), 349–368.
  * [18] P. Potočnik, S. Wilson, Tetravalent edge-transitive graphs of girth at most 4, Jour. Combin. Theory, ser. B, 97 (2007), 217–236.
  * [19] P. Potočnik, S. Wilson, Linking-ring structures and tetravalent semisymmetric graphs, Ars. Math. Contemporanea, 7 (2014), 341–352.
  * [20] C. P Rourke, B. J. Sanderson, Introduction to Piecewise-Linear Topology, Springer, New York, NY, 1972.
  * [21] D. Schattschneider Coxeter and the Artists: 2-Way Inspiration, in The Coxeter Legacy, Reflections and Projections, (ed. C. Davis et al.), Amer. Math. Soc., 2006.
  * [22] W. D. Wallis, One-Factorizations (Math. and its Appl.), Springer, NY, 1997.
  * [23] S. Wilson, Uniform maps on the Klein bottle, Jour. for Geom. and Graphics, 10(2) (2006), 161–171.
  * [24] S. Wilson, P. Potočnik, Recipes for edge-transitive graphs, arXiv:1608.04158.