ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.09
https://doi.org/10.26493/1855-3974.3221.5ga
(Also available at http://amc-journal.eu)
On z-monodromies in embedded graphs
Adam Tyc
Faculty of Mathematics and Computer Science, University of Warmia and Mazury,
Słoneczna 54, 10-710 Olsztyn, Poland
Received 9 September 2023, accepted 27 May 2024, published online 14 October 2024
Abstract
We characterize all permutations which occur as the z-monodromies of faces in con-
nected simple finite graphs embedded in surfaces whose duals are also simple.
Keywords: Central circuit, chess coloring, embedded graph, zigzag, z-monodromy.
Math. Subj. Class. (2020): 05C38, 05C10
1 Introduction
Zigzags are closed walks in embedded graphs which generalize the concept of Petrie poly-
gons in regular polyhedra [2]. They were used in computer graphics [6] and in enumerating
all combinatorial possibilities for fullerenes in mathematical chemistry [1, 4]. Zigzags are
also closely related to Gauss code problem: if an embedded graph contains a single zigzag,
then this zigzag is a geometrical realization of a certain Gauss code (see [5, Section 17.7]
for the planar case and [3, 9] for the case when a graph is embedded in an arbitrary surface).
More results on zigzags can be found in [8, 10, 13, 15].
We will consider zigzags in connected simple finite graphs embedded in surfaces whose
duals are also simple. The latter condition guarantees that for any two consecutive edges
on a face there is a unique zigzag containing them. This property is the crucial tool in the
concept of z-monodromy. For a face F , the z-monodromy MF is a permutation on the set
of all oriented edges obtained by orienting each edge of F in the two possible ways. If e0, e
is a pair of consecutive edges in F , then MF (e) is the first oriented edge of F that occurs
in the zigzag containing e0, e after e.
Such z-monodromies were introduced in [12] and exploited to prove that any triangu-
lation of an arbitrary (not necessarily oriented) closed surface can be shredded to a triangu-
lation with a single zigzag. There are precisely 7 types of z-monodromies for triangle faces
and each of them is realized. The properties and some applications of z-monodromies of
E-mail address: adam.tyc@matman.uwm.edu.pl (Adam Tyc)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P4.09
triangle faces can be found in [11, 16]. See also [14] for a generalization of z-monodromies
on pairs of edges.
Faces of embedded graph under consideration contains at least three edges. We char-
acterize permutations that occur as z-monodromies of k-gonal faces for any k ≥ 3. More
precisely, a permutation σ on the set
[k]± = {1, . . . , k,−k, . . . ,−1}
occurs as the z-monodromy if and only if it satisfies the following conditions:
• if σ(i) = j, then σ(−j) = −i;
• σ(i) 6= −i.
In the plane case, our construction is based on the chess coloring of 4-regular plane graphs.
For every permutation σ satisfying the above conditions there is a plane graph with a face
F whose z-monodromy is σ; furthermore, this graph contains a unbounded triangle face T
such that every zigzag passing through F does not pass through T . To extend the construc-
tion on the general case, we take any graph embedded in a surface with a triangle face and
replace this face by the above plane graph.
We consider the case when an embedded graph and its dual both are simple. In the
general case, zigzags cannot be reconstructed from pairs of consecutive edges. This shows
that the concept of z-monodromy cannot be generalized in a direct way.
2 Zigzags in embedded graphs
Let S be a connected closed 2-dimensional (not necessarily orientable) surface. Let Γ be
a 2-cell embedding of a connected finite graph in S, in other words, a map [7, Defini-
tion 1.3.6]. The difference S \ Γ is a disjoint union of open disks and the closures of these
disks are the faces. We say that a face is k-gonal if it contains precisely k edges. We will
always assume that the following condition is satisfied:
(SS) Γ and the dual map Γ∗ (see [7, p.52]) both are embeddings of simple graphs.
The fact that one of the graphs is simple does not implies that the same holds for the other
graph. For example, Γ∗ is not simple if Γ contains a vertex of degree 2 or two distinct faces
with intersection containing more than one edge. The condition (SS) implies that each face
in our graphs is k-gonal with k ≥ 3.
A zigzag in Γ is a sequence of edges {ei}i∈N satisfying the following conditions for
every i ∈ N:
• ei and ei+1 are distinct, they have a common vertex and belong to the same face,
• the faces containing ei, ei+1 and ei+1, ei+2 are distinct and the edges ei and ei+2 are
non-intersecting.
Since Γ is finite, there is a natural number n > 1 such that ei+n = ei for every natural
i. Thus, every zigzag will be represented as a cyclic sequence e1, . . . , en, where n is the
smallest number satisfying this condition.
Any zigzag is completely determined by every pair of consecutive edges contained in
this zigzag. Conversely, for every pair of distinct edges e, e′ which have a common vertex
A. Tyc: On z-monodromies in embedded graphs 3
and belong to the same face there is a unique zigzag containing the sequence e, e′. This
property will be used in the next section.
If Z = {e1, . . . , en} is a zigzag, then the reversed sequence Z−1 = {en, . . . , e1} also
is a zigzag. A zigzag cannot contain a sequence e, e′, . . . , e′, ewhich implies that Z 6= Z−1
for any zigzag Z. In other words, a zigzag cannot be self-reversed (see [12] for the proof
for triangulations; in our case the proof is similar).
Example 2.1. Consider the cube Q3 whose vertices are 1, . . . , 8, see Fig. 1.
1 2
4 3
5 6
8 7
Figure 1: The cube Q3
It contains precisely 4 zigzags up to reversing:
12, 23, 37, 78, 85, 51; 12, 26, 67, 78, 84, 41; 14, 43, 37, 76, 65, 51; 23, 34, 48, 85, 56, 62.
Let BPn be the n-gonal bipyramid, where 1, . . . , n are the consecutive vertices of the base
and the remaining two vertices are a, b.
3
2
1
a
b
.
Figure 2: The bipyramid BP3
If n = 3 (see Fig. 2), then it contains a single zigzag (up to reversing):
a1, 12, 2b, b3, 31, 1a, a2, 23, 3b, b1, 12, 2a, a3, 31, 1b, b2, 23, 3a.
The same holds for BPn if n is odd. If n is even, then BPn contains 2 or 4 zigzags up to
reversing.
Every zigzag in Γ induces in a natural way a zigzag in Γ∗ and vice versa.
Remark 2.2. Zigzags can be defined in maps of non-simple graphs [8]. In this case,
there are simple examples showing that a zigzag cannot be determined by any pair of its
consecutive edges.
4 Ars Math. Contemp. 24 (2024) #P4.09
3 Main result
Let Γ be as in the previous section and let F be a k-gonal face of Γ. Denote by v0, . . . , vk−1
the consecutive vertices of F in a fixed orientation on the boundary of this face (it is possi-
ble that vi = vj if |i− j| ≥ 3). Consider the set of all oriented edges of F
Ω(F ) = {e1, . . . , ek,−ek, . . . ,−e1},
where ei = vi−1vi and −ei = vivi−1 are mutually reversed oriented edges of F (the
indices are taken modulo k); it is clear that Ω(F ) consists of 2k mutually distinct elements.
Let DF be the following permutation on Ω(F )
DF = (e1, e2, . . . , ek)(−ek, . . . ,−e2,−e1).
In other words, DF transfers every oriented edge of F to the next oriented edge in the
corresponding orientation on the boundary.
The z-monodromy of F is the mapping MF : Ω(F ) → Ω(F ) defined as follows. For
any e ∈ Ω(F ) we take e0 ∈ Ω(F ) such that DF (e0) = e. There is a unique zigzag, where
e0, e are consecutive edges. The first element of Ω(F ) contained in this zigzag after e0, e
is denoted by MF (e).
Remark 3.1. The z-monodromy is defined when (SS) is satisfied. This concept cannot be
carried out on the general case immediately.
Lemma 3.2. The following assertions are fulfilled:
(1) If MF (e) = e′ for some e, e′ ∈ Ω(F ), then MF (−e′) = −e.
(2) MF is bijective.
(3) MF (e) 6= −e for every e ∈ Ω(F ).
Proof. (1). Let e ∈ Ω(F ). Consider e0 ∈ Ω(F ) satisfying DF (e0) = e. If Z is the zigzag
containing the pair e0, e, then
e′ = MF (e) and e′0 = DFMF (e)
are the next two elements of Ω(F ) in Z. Observe that DF (−e′0) = −e′. The reversed
zigzag Z−1 contains the sequence −e′0,−e′ and −e is the first element of Ω(F ) contained
in Z−1 after this pair. This means that MF (−e′) = −e.
(2). It is sufficient to show that MF is injective. Suppose that MF (e) = MF (e′) = e′′.
By (1), we have −e = MF (−e′′) = −e′ which implies that e = e′.
(3). Let e and e0 be as in the proof of (1). If MF (e) = −e, then there is a zigzag Z
containing the sequences e0, e and −e,DF (−e). Since DF (−e) = −e0, Z passes through
both pairs e0, e and −e,−e0. This implies that Z = Z−1 which is impossible.
The set Ω(F ) is naturally identified with
[k]± = [k]+ ∪ [k]−
where
[k]+ = {1, . . . , k}, and [k]− = {−k, . . . ,−1}
(ei and −ei correspond to i and −i, respectively). Then, by Lemma 3.2, the z-monodromy
MF is a permutation σ of [k]± satisfying the following conditions:
A. Tyc: On z-monodromies in embedded graphs 5
(M1) if σ(i) = j, then σ(−j) = −i;
(M2) σ(i) 6= −i.
Our main result is the following.
Theorem 3.3. Let S be a connected closed 2-dimensional (not necessarily orientable)
surface and let k ≥ 3. Let also σ be a permutation of [k]± satisfying (M1) and (M2).
There is a connected finite graph Γ embedded in S and satisfying (SS) which contains a
k-gonal face F whose z-monodromy is σ.
In Section 4, we prove Theorem 3.3 for plane graphs (graphs embedded in a sphere).
Graphs on surfaces different from a sphere will be considered in Section 5.
4 The plane case
4.1 Preliminary
Let G be a 4-regular plane graph. The dual graph G∗ is bipartite and there exists a chess
coloring of faces of G in two colors b and w. For c ∈ {b, w} we take a vertex inside
every face of G assigned with the color c and join two such vertices by an edge if the
corresponding faces have a common vertex at theirs boundaries. The obtained plane graph
will be denoted byRc(G). The graphsRb(G) andRw(G) are dual (see Fig. 3).
Figure 3: The chess coloring and the related graphs
Consider a plane graph Γ. The medial graph of Γ is the graphM(Γ) whose vertex set
is the edge set of Γ and two vertices ofM(Γ) are joined by an edge if they have a common
vertex and belong to the same face in Γ. The graph M(Γ) is also plane. This graph is
4-regular and its face set is the union of the vertex set and the face set of Γ. Thus,M(Γ) is
chess colored. Let b be the color used to coloring the faces ofM(Γ) corresponding to the
vertices of Γ. The remaining faces ofM(Γ) (corresponding to the faces of Γ) are colored
in w. Then
Rb(M(Γ)) = Γ and Rw(M(Γ)) = Γ∗.
For example, the graph marked in black in Fig. 3 is the medial graph of the graphs marked
in red and blue.
A central circuit is a circuit in the medial graph which is obtained by starting with an
edge and continuing at each vertex by the edge opposite to the entering one [4, p.5]. We will
consider central circuits as cyclic sequences of vertices and distinguish each central circuit
from the reversed. If Γ and Γ∗ both are simple, then there is a one-to-one correspondence
6 Ars Math. Contemp. 24 (2024) #P4.09
between zigzags in Γ and central circuits inM(Γ): a sequence formed by edges of Γ is a
zigzag if and only if this sequence is a central circuit inM(Γ). In Fig. 4. the part of the
zigzag is marked by the bold red line and the corresponding part of the central circuit is
marked by the bold black line.
Figure 4: A zigzag and the corresponding central circuit
4.2 Main construction
Let σ be a permutation on [k]± satisfying (M1) and (M2). We construct a 4-regular plane
graph G which is the medial graph of a plane graph, where σ occurs as the z-monodromy
of a face F (this plane graph contains a k-gonal face F such that σ is MF ).
Consider a circle C embedded in the plane. We take mutually distinct points p1, . . . , pk
from C such that these points occur along C in the clockwise order; these points will be the
edges of the mentioned above faceF . Next, denote byC ′ a circle inside the part of the plane
bounded by C and take mutually distinct points a12, a23, . . . , a(k−1)k, ak1 occurring on C ′
in the clockwise order. Similarly, let C ′′ be a circle inside the part of the plane bounded
by C ′ and let r1, lk, r2, l1, . . . , rk, lk−1 be mutually distinct points that occur along C ′′ in
the clockwise order. For every aij we take two segments that intersect precisely in aij and
join pi with li and pj with rj , respectively. Note that all such segments intersect each of
C,C ′, C ′′ in precisely one point and the interiors of any two of these segments are disjoint
if they contain distinct points aij . Denote by Si the union of the segment joining ri with
pi, the arc of C between pi and pi+1 and the segment joining pi+1 with li+1 if i < k; for
i = k we replace every index i+ 1 by 1. See Fig. 5 for the case k = 6.
p1
p2
p3p4
p5
p6
a12
a61
a56
a45
a34
a23
l1
l2
l3
l4
l5
l6r1 r2
r3
r4
r5
r6
S1
S2
S3
S4
S5
S6
Figure 5: The beginning of construction for k = 6
A. Tyc: On z-monodromies in embedded graphs 7
We will work with the relation ∼ on the set
O =
k⋃
i=1
{li, ri}
such that for any i, j ∈ [k]± satisfying σ(i) = j one of the following possibilities is
realized:
(1) li ∼ rj if i, j ∈ [k]+,
(2) r−i ∼ l−j if i, j ∈ [k]−,
(3) li ∼ l−j if i ∈ [k]+ and j ∈ [k]−,
(4) r−i ∼ rj if i ∈ [k]− and j ∈ [k]+.
The relation ∼ is irreflexive and symmetric. Indeed, if li ∼ li (the case (3)) or ri ∼ ri
(the case (4)), then we get σ(i) = −i which contradicts (M2). Thus, ∼ is irreflexive.
Now, we show that if li ∼ lj , then lj ∼ li (the remaining three cases are similar). If
li ∼ lj with i, j ∈ [k]+ (the case (3)), then σ(i) = −j and, by (M1), σ(j) = −i and
j ∈ [k]+,−i ∈ [k]−; i.e. lj ∼ li. Note that for each x ∈ O there is a unique x′ ∈ O such
that x ∼ x′.
If a pair of points from O is in the relation ∼, then we join them by a curve homeo-
morphic to the segment [0, 1] inside the part of the plane bounded by C ′′. The following
conditions must be satisfied:
• the curves have no more than finitely many intersections and self-intersections,
• for every such intersection point either there are precisely two distinct curves passing
once through this point or there is a single curve passing twice through it,
• all intersections are transversal.
Let L1, . . . , Lk be the curves described above (we take an arbitrary numeration that does
not depend on the endpoints from O).
Note that each of l1, r1, . . . , lk, rk is a common point of a unique Si and a unique Lj .
Thus, we obtain a family C of closed curves
Si1 ∪ Li1 ∪ Si2 ∪ Li2 ∪ . . .
such that every Si and Lj is contained in precisely one of these curves. Let V be the set of
all intersection and self-intersection points of curves from C. In particular, all pi and all aij
belong to V .
Example 4.1. Let k = 6 and
σ = (1,−6,−4, 2)(3,−5)(5,−3)(−2, 4, 6,−1).
The relation ∼ on the set O = {l1. . . . , l6, r1, . . . , r6} is as follows
l1 ∼ l6, r6 ∼ l4, r4 ∼ r2, l2 ∼ r1, l3 ∼ l5, r5 ∼ r3.
One of suitable connections between points from O is presented in Fig. 6.
8 Ars Math. Contemp. 24 (2024) #P4.09
p1
p2
p3p4
p5
p6
a12
a61
a56
a45
a34
a23
l1
l2
l3
l4
l5
l6r1
r2
r3
r4
r5
r6
Figure 6: A suitable connection between points of O
In this case, C consists of precisely 3 closed curves with 17 intersection points, i.e. |V | =
17.
Let G = G(C) be the graph whose vertex set is V and two vertices are joined by an
edge if they are two consecutive points on one of curves from C. In fact, we consider G as
a graph whose vertices are points on the plane and edges are parts of curves from C joining
these points. It is easy to see thatG is a 4-regular and the curves from C correspond to pairs
of mutually reversed central circuits from G. We make the chess coloring of G and split
the set of its faces into the two sets corresponding to the colors. Let b be the color of faces
whose boundaries are cycles with vertices pi, pj , aij ; as above, w is the other color.
As in Subsection 4.1, we obtain the dual graphs Rb(G) and Rw(G). These graphs are
not necessarily simple; they may contain the following fragments:
(A) loops,
(B) multiple edges,
(C) edges that belong to the boundary of one face only (in particular, edges with vertices
of degree 1),
(D) pairs of faces whose intersection of boundaries contains more than one edge.
If one of the cases (A) or (B) occurs in one of the graphsRb(G),Rw(G), then the case (C)
or (D), respectively, occurs in the dual graph.
Example 4.2. Let C be as in Example 4.1. The graphs Rb(G) and Rw(G) are presented
in Fig. 7a and Fig. 7b, respectively.
A. Tyc: On z-monodromies in embedded graphs 9
p1
p2
p3p4
p5
p6
a12
a61
a56
a45
a34
a23
l1
l2l3
l4
l5
l6r1 r2
r3
r4
r5
r6
p1
p2
p3p4
p5
p6
a12
a61
a56
a45
a34
a23
l1
l2
l3
l4
l5
l6r1
r2
r3
r4
r5
r6
(a) (b)
Figure 7: The dual graphsRb(G) andRw(G)
The graph Rb(G) contains a pair of faces with two common edges (the case (D)) which
corresponds to a double edge inRw(G) (the case (B)).
Now, we show how modify the graph G such that the connections between the points
from O induced by the relation ∼ do not change and the graphs Rb(G),Rw(G) become
simple.
Suppose that e is an edge joining the vertices v′ and v′′ in Rb(G) or Rw(G) (both the
cases are similar). We consider separately the cases v′ 6= v′′ and v′ = v′′ (see Fig. 8a
and 8b, respectively). If v′ 6= v′′, then we consider the following edges in the same graph
(Rb(G) orRw(G)):
• e′+ and e′− which occur directly after e in the clockwise and the anticlockwise order
on edges incident to v′, respectively;
• e′′+ and e′′− which occur directly after e in the clockwise and the anticlockwise order
on edges incident to v′′, respectively.
If v′ = v′′, then we exclude the case when the loop e is the boundary of a face (this case
will be considered separately). The edge e splits the plane into two parts and we consider
the following edges:
• e′+ and e′− are the edges contained in one of these parts which occur directly after e
in the clockwise and the anticlockwise order on edges incident to v′, respectively;
• e′′+ and e′′− are the edges contained in the other part of the plane which occur directly
after e in the clockwise and the anticlockwise order on edges incident to v′′, respectively.
There are precisely two parts of central circuits in G (up to reversing) that pass through e
(since e, e′δ, e
′′
δ are vertices of G, where δ ∈ {+,−}):
. . . , e′+, e, e
′′
+, . . . and . . . , e
′
−, e, e
′′
−, . . .
which are marked in blue and red in Fig. 8.
10 Ars Math. Contemp. 24 (2024) #P4.09
v′ v′′e
e′+ e
′′
−
e′− e
′′
+ e
′
−
e′+
e′′+
e′′−
e
v′
(a) (b)
Figure 8: Parts of central circuits
For each of these cases we replace e by the graphs presented in Fig. 9a and Fig. 9b,
respectively.
v′ v
′′
e′+ e′′−
e′− e
′′
+ e′−
e′+
e′′+
e′′−
v′
(a) (b)
Figure 9: Two types of expansion
This operation will be called the expansion of e. It replaces the edge e by an intersecting
trail Eδ , δ ∈ {+,−}, joining e′δ and e′′δ . So, the mentioned above parts of central circuits
will be replaced by
. . . , e′+, E+, e
′′
+, . . . and . . . , e
′
−, E−, e
′′
−, . . . ,
respectively (they are marked in blue and red in Fig. 9). Thus, central circuits do not
change in a significant way.
Remark 4.3. We can obtain the same result using other pairs of graphs instead of the
graphs from Fig. 9. This pair is the first which we found.
Now, we explain how transform Rb(G),Rw(G) to simple graphs if at least one of the
possibilities (A)–(D) occurs. Without loss of generality we can consider Rb(G). Further-
more, we restrict ourselves to the cases (A) and (B) (since (C) and (D) correspond to (A)
and (B), respectively, in the dual graph). The case (A) will be decomposed in two subcases.
(A1). Suppose that Rb(G) contains a face whose boundary is a loop. The correspond-
ing parts of mutually reversed central circuits from G are also loops. The loops can be
removed from these graphs without changing the central circuits in a significant way (see
Fig. 10).
A. Tyc: On z-monodromies in embedded graphs 11
Figure 10: Removing a loop
(A2). If e is a loop in Rb(G) which is not a boundary of a face, then we use the
expansion to e.
(B). If two distinct vertices are connected by m ≥ 2 edges, then we expand any m− 1
of them.
Example 4.4. Since Rw(G) from Example 4.2 contains two edges connecting the same
pair of vertices (the case (C)), we expand one of these edges, see Fig. 11.
Figure 11: The expansion of an edge inRw(G)
This simultaneously modify Rb(G) and we obtain a graph without the possibility (A), see
Fig. 12.
Figure 12: The corresponding modification ofRb(G)
So, we can simultaneously transform Rb(G) and Rw(G) to simple graphs such that
the relation ∼ on elements of O is not changed. In particular, we come to a new (4-
regular plane) graph G and assert that Rb(G) contains a face for which σ occurs as the
z-monodromy of one of faces.
12 Ars Math. Contemp. 24 (2024) #P4.09
Recall that C is a cycle in G with the vertices p1, . . . , pk and it is the boundary of the
outer face of G. This face has a common edge only with faces whose boundaries contain
the vertices pi, pj , aij . By the definition ofRb(G), we have the following:
• every face with the boundary containing pi, pj , aij in G is a vertex in Rb(G) which
we denote by vij ;
• the face bounded by C in G is a face inRb(G) which will be denoted by F ;
• every pi corresponds to an edge of F .
Consider the oriented edges ej = vijvjl and −ej = vjlvij in Rb(G), where i, j, l are
three consecutive elements in the cyclic sequence 1, . . . , k. The pair of mutually reversed
oriented edges ej ,−ej corresponds to the vertex pj in G. Thus,
Ω(F ) = {e1, . . . , ek,−ek, . . . ,−e1}.
Let e0, e ∈ Ω(F ) be such that DF (e0) = e. There is a unique zigzag Z inRb(G) contain-
ing the pair e0, e. The element e′ which occurs in Z directly after this pair does not belong
to Ω(F ). The edges e0, e, e′ are three consecutive vertices in the central circuit in G corre-
sponding to Z such that e0, e are two consecutive vertices from the cycle C and e′ is one
of elements aij . Let x be the first element from O such that the central circuit containing
e0, e, e
′ passes through x (as a curve on the plane) directly after this triple (x is a point on
the plane, but not a vertex of the graph). There is a unique x′ ∈ O such that x ∼ x′ and
the central circuit passes through x′. Since there is no elements of Ω(F ) between x and x′
in the central circuit, the first element of Ω(F ) that occurs after x′ corresponds to MF (e).
Therefore, σ occurs as MF .
Example 4.5. Let F be the outer face ofRb(G) from Example 4.4 and let ei be the oriented
edge of F corresponding to pi whose direction is defined by the clockwise orientation on
the boundary of F (see Fig. 13).
e1
e2
e3e4
e5
e6
Figure 13: The new graphRb(G)
A direct verification shows that
MF = (e1,−e6,−e4, e2)(e3,−e5)(e5,−e3)(−e2, e4, e6,−e1),
i.e. the permutation
σ = (1,−6,−4, 2)(3,−5)(5,−3)(−2, 4, 6,−1)
from Example 4.1 occurs as MF inRb(G).
A. Tyc: On z-monodromies in embedded graphs 13
5 The non-plane case
In this section, we consider an arbitrary connected closed 2-dimensional (not necessarily
orientable) surface S different from a sphere. We show that any permutation σ on [k]±
satisfying (M1) and (M2) occurs as the z-monodromy of k-gonal face in a graph embedded
in S. Let Γ be a graph embedded in a sphere (a plane graph) such that σ occurs as the
z-monodromy of a face F of Γ. We assume that Γ = Rb(G), where G is the 4-regular
graph from Section 4.
Let e be an edge in G. It is contained in the boundaries of precisely two faces F1, F2
in G. We assume that F1 and F2 correspond to a face distinct from F and a vertex of Γ,
respectively. Let us take three circles B1, B2, B3 that intersect like the Borromean rings.
Consider the graph G′ obtained from G by adding B1, B2, B3 as in Fig. 14.
B2
B1 B3
e
F1
F2
Figure 14: Constructing of G′
It must be pointed out that the circlesB1, B2, B3 do not intersect the remaining edges ofG.
The graph G′ is 4-regular andRb(G′) is obtained from Γ = Rb(G) by adding the graph G̃
marked in red in Fig. 15 to the vertex v corresponding to the face F2.
B2
B1 B3
e
v
T
F1
F2
Figure 15: The graph G̃
It is clear that Rb(G′) and Rw(G′) are simple. Denote by T the face of G̃ which is con-
tained in F2 and does not contain v. Note that B1, B2, B3 induce central circuits of G′.
Each zigzag ofRb(G′) passing through T corresponds to one of Bi. Observe that F is the
face of Rb(G′) and the zigzags corresponding to B1, B2, B3 do not contain edges of this
face. This means that the z-monodromy of F inRb(G′) is also σ.
Consider any graph Γ′ embedded in S that contains a triangle face T ′. We take the
connected sum of the sphere containing Rb(G′) and S by removing the interiors of faces
14 Ars Math. Contemp. 24 (2024) #P4.09
T and T ′ and identifying theirs boundaries by a homeomorphism that sends vertices to
vertices. We come to a new graph embedded in S containing F as a face. Since every
zigzag of Rb(G′) containing an edge of F does not pass through any edge of T , the z-
monodromy of F in the new graph is the same as in Rb(G′) and, consequently, as in
Rb(G).
ORCID iDs
Adam Tyc https://orcid.org/0000-0003-4870-5731
References
[1] G. Brinkmann and A. W. M. Dress, PentHex puzzles: a reliable and efficient top-down approach
to fullerene-structure enumeration, Adv. in Appl. Math. 21 (1998), 473–480, doi:10.1006/aama.
1998.0608, https://doi.org/10.1006/aama.1998.0608.
[2] H. S. M. Coxeter, Regular polytopes, Dover Publications, Inc., New York, 3rd edition, 1973.
[3] H. Crapo and P. Rosenstiehl, On lacets and their manifolds, volume 233, pp. 299–320, 2001,
doi:10.1016/S0012-365X(00)00248-X, graph theory (Prague, 1998), https://doi.org/
10.1016/S0012-365X(00)00248-X.
[4] M.-M. Deza, M. Dutour Sikirić and M. I. Shtogrin, Geometric structure of chemistry-relevant
graphs, volume 1 of Forum for Interdisciplinary Mathematics, Springer, New Delhi, 2015, doi:
10.1007/978-81-322-2449-5, zigzags and central circuits, https://doi.org/10.1007/
978-81-322-2449-5.
[5] C. Godsil and G. Royle, Algebraic graph theory, volume 207 of Graduate Texts in Mathematics,
Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9, https://doi.org/
10.1007/978-1-4613-0163-9.
[6] Ø. Hjelle and M. Dæhlen, Triangulations and applications, Mathematics and Visualization,
Springer-Verlag, Berlin, 2006.
[7] S. K. Lando and A. K. Zvonkin, Graphs on surfaces and their applications, volume 141
of Encyclopaedia of Mathematical Sciences, Springer-Verlag, Berlin, 2004, doi:10.1007/
978-3-540-38361-1, with an appendix by Don B. Zagier, Low-Dimensional Topology, II,
https://doi.org/10.1007/978-3-540-38361-1.
[8] S. Lins, Graph-encoded maps, J. Combin. Theory Ser. B 32 (1982), 171–181, doi:10.1016/
0095-8956(82)90033-8, https://doi.org/10.1016/0095-8956(82)90033-8.
[9] S. Lins, E. Oliveira-Lima and V. Silva, A homological solution for the Gauss code problem in
arbitrary surfaces, J. Combin. Theory Ser. B 98 (2008), 506–515, doi:10.1016/j.jctb.2007.08.
007, https://doi.org/10.1016/j.jctb.2007.08.007.
[10] M. Pankov and A. Tyc, Connected sums of z-knotted triangulations, European J. Combin. 80
(2019), 326–338, doi:10.1016/j.ejc.2018.02.010, https://doi.org/10.1016/j.ejc.
2018.02.010.
[11] M. Pankov and A. Tyc, On two types of z-monodromy in triangulations of surfaces, Discrete
Math. 342 (2019), 2549–2558, doi:10.1016/j.disc.2019.05.030, https://doi.org/10.
1016/j.disc.2019.05.030.
[12] M. Pankov and A. Tyc, z-knotted triangulations of surfaces, Discrete Comput. Geom.
66 (2021), 636–658, doi:10.1007/s00454-020-00182-3, https://doi.org/10.1007/
s00454-020-00182-3.
A. Tyc: On z-monodromies in embedded graphs 15
[13] H. Shank, The theory of left-right paths, in: Combinatorial mathematics, III (Proc. Third Aus-
tralian Conf., Univ. Queensland, St. Lucia, 1974), Springer, Berlin-New York, volume Vol. 452
of Lecture Notes in Math., pp. 42–54, 1975.
[14] A. Tyc, z-knotted and z-homogeneous triangulations of surfaces, Discrete Math. 344 (2021),
Paper No. 112405, 13, doi:10.1016/j.disc.2021.112405, https://doi.org/10.1016/
j.disc.2021.112405.
[15] A. Tyc, Z-oriented triangulations of surfaces, Ars Math. Contemp. 22 (2022), Paper No. 2,
17, doi:10.26493/1855-3974.2242.842, https://doi.org/10.26493/1855-3974.
2242.842.
[16] A. Tyc, Zigzags in combinatorial tetrahedral chains and the associated markov chain, Dis-
crete Comput. Geom. (2024), doi:10.1007/s00454-024-00631-3, https://doi.org/10.
1007/s00454-024-00631-3.