ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 25 (2025) #P2.05
https://doi.org/10.26493/1855-3974.3023.c45
(Also available at http://amc-journal.eu)
Upper embeddability of graphs and products of
transpositions associated with edges*
Shuhei Tsujie †
Department of Mathematics, Hokkaido University of Education,
Asahikawa, Hokkaido 070-8621, Japan
Ryo Uchiumi
Department of Mathematics, Graduate School of Science, Osaka University,
Toyonaka, Osaka 560-0043, Japan
Received 4 December 2022, accepted 12 April 2024, published online 13 March 2025
Abstract
Given a graph, we associate each edge with the transposition which exchanges the
endvertices. Fixing a linear order on the edge set, we obtain a permutation of the vertices.
Dénes proved that the permutation is a full cyclic permutation for any linear order if and
only if the graph is a tree.
In this article, we characterize graphs having a linear order such that the associated
permutation is a full cyclic permutation in terms of graph embeddings. Moreover, we give
a counterexample for Eden’s question about an edge ordering whose associated permutation
is the identity.
Keywords: Full cyclic permutation ordering, upper-embeddable graph, 2-cell embedding, rotation
system.
Math. Subj. Class. (2020): 05C25, 05C10, 57M15
*The authors wish to thank Professor Sachiko Saito for her valuable comments about topics of topology. The
authors would also like to express their deepest appreciation to the anonymous referee for careful reading and
pointing out a deficiency in a proof.
†Corresponding author.
E-mail addresses: tsujie.shuhei@a.hokkyodai.ac.jp (Shuhei Tsujie), uchiumi.ryou.1xu@ecs.osaka-u.ac.jp
(Ryo Uchiumi)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 25 (2025) #P2.05
1
2
3
4
5
e1
e2
e3
e4
e5
e6
Figure 1: A butterfly graph. Figure 2: A dumbbell graph.
1 Introduction
In this article, a graph G stands for a connected multigraph G = (VG, EG, rG), where
• VG is a finite set of vertices,
• EG is a finite set of edges,
• rG is a map from EG to
(
VG
2
)
, the collection of subsets of VG consisting of 2 ele-
ments.
Note that rG(e) represents the endvertices of the edge e. Also note that loops are not
allowed.
Let n be a positive integer and suppose that VG = [n] := {1, 2, . . . , n}. When an edge
e ∈ EG satisfies rG(e) = {u, v}, we associate the transposition τe := (u v) ∈ Sn with the
edge e, where Sn denotes the symmetric group of degree n.
An edge ordering of a graph G is a linear order ≤ω on EG, denoted as a sequence
ω = (e1, . . . , em) in which ei <ω ej if and only if i < j. Given an edge ordering
ω = (e1, . . . , em), we associate the product πω := τem · · · τe1 ∈ Sn.
Definition 1.1. A permutation σ ∈ Sn is called a full cyclic permutation if σ is a cyclic
permutation of length n. An edge ordering ω = (e1, . . . , em) of a graph G is a full cyclic
permutation ordering if the corresponding permutation πω = τem · · · τe1 is a full cyclic
permutation.
Dénes proved the following theorem to state a connection between labeled trees and
factorization of a full cyclic permutation into transpositions.
Theorem 1.2 (Dénes [1]. See also [7, Section 2] and [11, Lemma 2.1]). Given a graph G,
the following are equivalent.
(i) Any edge ordering of G is a full cyclic permutation ordering.
(ii) G is a tree.
Note that Theorem 1.2 plays an important role in the studies of the chromatic symmetric
functions and the chromatic operator for trees [3, 11]. Also, note that recently the second
author [16] studied an analogue of Theorem 1.2 for signed graphs and the hyperoctahedral
group.
It is a natural question to ask what graphs admit a full cyclic permutation ordering. For
example, let G be the butterfly graph pictured in Figure 1 and define the edge ordering ω
by ω := (e1, e2, e3, e4, e5, e6). Then
πω = τe6τe5τe4τe3τe2τe1 = (3 5)(1 3)(4 5)(3 4)(2 3)(1 2) = (1 3 2 5 4).
S. Tsujie and R. Uchiumi: Upper embeddability of graphs and products of transpositions . . . 3
Therefore ω is a full cyclic permutation ordering of the butterfly graph G.
Let β(G) := |EG|−|VG|+1 denote the Betti number (also called the circuit rank) of the
connected graphG. When a graphG has a full cyclic permutation ordering, considering the
signature of a full cyclic permutation ordering, one can show that the Betti number β(G) is
even. However, the converse is false. For example, the dumbbell graph (Figure 2) has no
full cyclic permutation orderings although its Betti number is 2.
We regard a graph as a topological space by identifying each edge with the unit interval
[0, 1] and gluing them at vertices. Then β(G) coincides with the Betti number of G as
a topological space. In this article, we will show that having a full cyclic permutation
ordering is a topological property as follows.
Let Σ be an orientable closed surface and ι : G→ Σ an embedding. We call a connected
component of the complement of the image of ι a face. An embedding ι is a 2-cell embed-
ding if every face is homeomorphic to an open disk. For any 2-cell embedding ι : G → Σ,
|VG| − |EG|+ fι = 2− 2gΣ,
where fι denotes the number of faces of the 2-cell embedding ι and gΣ the genus of Σ.
Then
2gΣ + fι = β(G) + 1.
Therefore maximizing the genus gΣ is equivalent to minimizing the number of faces fι.
Hence the maximum genus γmax(G), the maximum of genus gΣ such that there exists a
2-cell embedding G→ Σ, satisfies
γmax(G) ≤
⌊
β(G)
2
⌋
,
where ⌊ ⌋ denotes the floor function. If the equality holds, then we say that G is upper
embeddable.
Upper embeddable graphs are well-studied objects by many researchers [4, 5, 8, 9, 10,
12, 13, 14, 15, 17, 18]. Jungerman and Xuong gave a combinatorial characterization of
upper embeddability independently.
Theorem 1.3 (Jungerman [5, Theorem 2], Xuong [18, Theorem A]). A connected graph
G with even (odd) Betti number is upper embeddable if and only if there exists a spanning
tree T of G such that all (all but one) connected components of G \ T consists of an even
number of edges.
Here is the main theorem of this article.
Theorem 1.4. Given a graph G, the following are equivalent.
(1) G has a full cyclic permutation ordering.
(2) There exists a 2-cell embedding ι : G→ Σ such that fι = 1.
(3) The Betti number β(G) is even and G is upper embeddable, that is, β(G) =
2γmax(G).
(4) There exists a spanning tree T of G such that every connected components of
G \ T consists of an even number of edges.
4 Ars Math. Contemp. 25 (2025) #P2.05
1
2
3
4
5 1
2
34 5
Figure 3: A 2-cell embedding of the butterfly graph into a torus with exactly one face.
Note that the conditions (2), (3), and (4) are equivalent by the definition of upper em-
beddability and Theorem 1.3. Figure 3 shows how the butterfly graph can be embedded
into a torus with exactly one face.
The organization of this article as follows. In Section 2, we will prove that (3) implies
(1) and give an example of constructing a full cyclic permutation ordering. In Section 3,
we will review the relation of 2-cell embeddings and rotation systems and we will prove
that (1) implies (2). Combining the proofs in Section 2 and Section 3, we will complete the
proof of Theorem 1.4.
In Section 4, we will study another extreme condition, that is, edge orderings ω such
that πω is the identity permutation, which Eden [2] studied. Eden gave necessary condi-
tions for such orderings and asked whether the condition is also sufficient. We will give a
counterexample for this question.
2 Proof that (3) implies (1)
First, we introduce the following lemma.
Lemma 2.1. Let π be a full cyclic permutation in Sn. If the distinct numbers u, v, w appear
in π in this cyclic order, then the product (u v)(v w)π is a full cyclic permutation.
Proof. By the assumption, we can write
π = (u a1 · · · ar v b1 · · · bs w c1 · · · ct),
where ai, bi, ci denote distinct numbers in [n] \ {u, v, w}. Then we obtain
(u v)(v w)π = (u v)(v w)(u a1 · · · ar v b1 · · · bs w c1 · · · ct)
= (u a1 · · · ar w c1 · · · ct v b1 · · · bs),
which is a full cyclic permutation.
We say that two edges e and e′ are adjacent if rG(e) ∩ rG(e′) ̸= ∅, that is, they have a
common endvertex. Note that the case rG(e) = rG(e′) is allowed.
Lemma 2.2. Let e and e′ be two adjacent edges in a graph G. If G \ {e, e′} has a full
cyclic permutation ordering, then G has a full cyclic permutation ordering.
Proof. Let ω′ = (e1, . . . , em) be a full cyclic permutation ordering of G \ {e, e′}. If
rG(e) = rG(e
′), then ω := (e1, . . . , em, e′, e) is a full cyclic permutation ordering of G
since πω = πω′ .
S. Tsujie and R. Uchiumi: Upper embeddability of graphs and products of transpositions . . . 5
1
2 3
4
5
W5
1
2 3
4
5
T
1
2 3
4
5
W5 \ T
Figure 4: Wheel graph W5 and its spanning tree T .
Now, suppose that rG(e) = {u, v} and rG(e′) = {v, w} with u ̸= w. If the cycle
order of u, v, w in πω′ is u, v, w, then ω := (e1, . . . , em, e′, e) is a full cyclic permutation
ordering of G by Lemma 2.1. In a symmetrical manner, if the cycle order is w, v, u, then
let ω := (e1, . . . , em, e, e′).
The following lemma is required.
Lemma 2.3 (Xoung [17, Lemma 3]). Suppose that G is upper embeddable and β(G) is
even. If G is not a tree, then there exist two adjacent edges e and e′ such that G \ {e, e′} is
upper embeddable.
Proof that (3) implies (1) in Theorem 1.4. We will show that G has a full cyclic permuta-
tion ordering by induction on the Betti number β(G). When β(G) = 0, G is a tree and has
a full cyclic permutation ordering by Dénes’ theorem (Theorem 1.2).
Assume β(G) > 0. By Lemma 2.3, there exist two adjacent edges e and e′ such that
G′ := G \ {e, e′} is upper embeddable. By the induction hypothesis, G′ has a full cyclic
permutation ordering. By Lemma 2.2, G has a full cyclic permutation ordering.
Example 2.4. Consider the wheel graph W5 pictured in Figure 4. The Betti number of
W5 is 4. Let T be the spanning tree of W5 consisting of the edges 12, 23, 34, 45. Then
W5 \ T is connected and consisting of 4 edges. Therefore W5 satisfies the condition (4)
in Theorem 1.4 and hence has a full cyclic permutation ordering. We will construct a full
cyclic permutation ordering following by the proof of Lemma 2.2.
We partition the edges of W5 \T into two adjacent pairs {25, 35} and {14, 15}. Define
the edge ordering ω1 of T by ω1 := (12, 23, 34, 45). By Dénes’ theorem (Theorem 1.2),
πω1 is a full cyclic permutation. Indeed we have
πω1 = (4 5)(3 4)(2 3)(1 2) = (2 1 5 4 3).
Next we define the edge ordering ω2 of T ∪ {25, 35}. Following the proof above, define
ω2 by ω2 := ω1 ∗ (35, 25), where ∗ denotes the concatenation. Then
πω2 = (2 5)(3 5)(2 1 5 4 3) = (4 2 1 3 5).
Similarly, define ω3 by ω3 := ω2 ∗ (15, 14). Then
πω3 = (1 4)(1 5)(4 2 1 3 5) = (4 2 5 1 3).
Thus we obtain a full cyclic permutation ordering ω3 = (12, 23, 34, 45, 35, 25, 15, 14) of
W5.
6 Ars Math. Contemp. 25 (2025) #P2.05
3 Proof that (1) implies (2)
Let IG(v) denote the set of edges of G incident to a vertex v ∈ VG. A rotation system of
G is a collection ρ = (ρv)v∈VG consisting of cyclic orders ρv on IG(v), where a cyclic
order on IG(v) is an equivalence class of linear orders on IG(v) obtained by identifying
(e1, e2, . . . , es) with its circular shift (e2, . . . , es, e1), denoted by [e1, . . . , es].
Every embedding of G on an orientable closed surface defines a rotation system with
the clockwise ordering for each vertex. Conversely, from a rotation system, we can obtain
a 2-cell embedding of G on an orientable closed surface as follows.
Define DG by
DG := { (e, u) ∈ EG × VG | u ∈ rG(e) } .
We call an element of DG a dart. When rG(e) = {u, v}, the dart (e, u) shows an orien-
tation of the edge e from the source u to the target v. Define the involution α on DG by
α(e, u) := (e, v).
Given a rotation system ρ = (ρv)v∈VG , we will define bijections σ and ϕ from DG
to itself. Suppose that ρv = [e1, . . . , es]. Define σ by σ(ei, v) := (ei+1, v), where we
consider es+1 = e1. Let ϕ := σ ◦ α.
For every dart d, the target of d coincides with the source of ϕ(d). Therefore each orbit
in DG/⟨ϕ⟩ determines a closed walk on G and we can make a polygon whose sides are
formed by the darts in the orbit. Gluing the sides of the polygons obtained from the orbits
in DG/⟨ϕ⟩ by the involution α, we obtain an embedding of G on a closed surface. One
can show that this surface is actually orientable (See [6, Subsection 3.2]) and hence this
embedding is the desired 2-cell embedding.
Theorem 3.1 ([6, Theorem 3.2.4]). Given a graph G, there exists a one-to-one corre-
spondence between rotation systems of G and 2-cell embeddings of G on oriented closed
surfaces up to orientation-preserving homeomorphism.
Note that, from the construction, the number of the faces of the embedding correspond-
ing to a rotation system is equal to the number of the orbits in DG/⟨ϕ⟩.
Let ω be an edge ordering of G. For each v ∈ VG, let ωv denote the linear order on
IG(v) induced by ω. Moreover, let ρω,v be the cyclic order on IG(v) determined by ωv .
Thus we obtain the rotation system ρω := (ρω,v)v∈VG from an edge ordering ω and hence
the corresponding bijections σω and ϕω = σω ◦ α.
Lemma 3.2. Let ω = (e1, . . . , em) be an edge ordering of a graph G. For each v ∈ VG,
let fv denote the minimal edge in IG(v) with respect to ω. Define a map Ψ: VG/⟨πω⟩ →
DG/⟨ϕω⟩ by
Ψ([v]) := [(fv, v)],
where the brackets denote equivalence classes. Then Ψ is a bijection.
Proof. First, we will show that the map Ψ is well-defined. It is sufficient to show that
[(fv, v)] = [(fπω(v), πω(v))] for each v ∈ VG.
Fix v ∈ VG. The edge ordering ω = (e1, . . . , em) defines the set Tv as follows.
Tv := { ei ∈ EG | (τiτi−1 · · · τ1)(v) ̸= (τi−1 · · · τ1)(v) } ,
S. Tsujie and R. Uchiumi: Upper embeddability of graphs and products of transpositions . . . 7
where we agree with (τi−1 · · · τ1)(v) = v if i = 1. Suppose that Tv = { ej1 , ej2 , . . . , ejs }
with j1 < j2 < · · · < js. Then (ej1 , . . . , ejs) is a trail from v to πω(v). Let v0 := v and
for k ∈ {1, . . . , s} define vk recursively as the endvertex of ejk other than vk−1. Note that
vs = πω(v).
From the definition of Tv , for each k ∈ {1, . . . , s− 1}, ejk+1 covers ejk in IG(vk) with
respect to ω. Therefore ϕω(ejk , vk−1) = (ejk+1 , vk). Since ejs is the maximal element in
IG(vs) with respect to the order ω, we have ϕω(ejs , vs−1) = (fvs , vs) = (fπω(v), πω(v)).
Thus Ψ is well-defined.
Next, to prove the surjectivity, take an orbit W ∈ DG/⟨ϕω⟩. Let f be the minimal
element in
{ e ∈ EG | (e, v) ∈W for some v ∈ VG }
with respect to ω. Suppose (f, v) ∈W . Assume f is not minimal in IG(v) with respect to
ωv . Then f ′ := σ−1ω (f) is less than f in IG(v) with respect to ω. Let rG(f
′) = {v, v′}.
Then ϕω(f ′, v′) = (f, v) and hence (f ′, v′) ∈ W . This contradicts to the minimality of f .
Therefore f is minimal in IG(v) and hence f = fv . Hence Ψ([v]) = [(f, v)] =W .
Finally, we prove the injectivity. Let u, v ∈ VG and suppose that Ψ([u]) = Ψ([v]).
Then we have ϕsω(fu, u) = (fv, v) for some s ∈ Z. Without loss of generality, we can
assume that s > 0.
Recall the edges of G are ordered by ω = (e1, . . . , em). We can write the edge fu as
fu = ej0 with some j0 ∈ {1, . . . ,m}. Moreover we can obtain the walk (ej0 , ej1 , . . . , ejs)
by (ejk , vk) := ϕω(ejk−1 , vk−1) for k ∈ {1, . . . , s}, where v0 := u. Note that (ej0 , v0) =
(fu, u) and (ejs , vs) = (fv, v). Suppose that
{ k ∈ {1, . . . , s} | jk−1 ≥ jk } = {p1, . . . , pt}
with p1 < · · · < pt = s. Then πiω(v0) = vjpi for i ∈ {1, . . . , t}. In particular, π
t
ω(u) =
πtω(v0) = vjpt = vs = v. Thus [u] = [v] and hence f is injective.
Now we are ready to prove that (1) implies (2).
Proof that (1) implies (2) in Theorem 1.4. Let ω be a full cyclic permutation ordering of
G. Then the number of faces of the 2-cell embedding corresponding to the rotation system
ρω is equal to |DG/⟨ϕω⟩| = |VG/⟨πω⟩| = 1.
4 Identity permutation ordering
In this section, a graph is not necessarily connected. We say that an edge ordering ω of a
graph G is an identity permutation ordering if πω = ε, where ε denotes the identity permu-
tation. Every edgeless graph vacuously has an identity permutation ordering. The minimal
example of a non-trivial graph having an identity permutation ordering is the 2-cycle C2.
Eden [2] studied simple graphs that have an identity permutation ordering and mentioned
the complete graph K4 is the minimal example. Figure 5 shows identity permutation or-
derings of C2 and K4.
Eden gave necessary conditions (without proof) for simple connected graphs having an
identity permutation ordering as follows.
8 Ars Math. Contemp. 25 (2025) #P2.05
1 2
e1
e2
1
2 3
4
e1
e3
e5
e6
e4
e2
Figure 5: The 2-cycleC2 and the complete graphK4 have an identity permutation ordering.
Proposition 4.1 (Eden [2, page 130]). Let G be a simple connected graph on n vertices
with m edges. If G has an identity permutation ordering, then the following conditions
hold.
(1) m is even.
(2) There exist a set C consisting of closed trails and a map ψ : VG → C such that the
following conditions hold.
(i) ψ is bijective.
(ii) Every v ∈ VG belongs to the closed trail ψ(v).
(iii) The sum of the number of edges of closed trails in C is 2m.
(iv) Each edge of G belongs to exactly two closed trails in C.
Proof. Suppose that ω = (e1, . . . , em) be an identity permutation ordering. Since the
identity permutation is an even permutation, we have m is even. Let Ψ: VG → DG/⟨ϕω⟩
be the bijection considered in Lemma 3.2. Note that VG = VG/⟨πω⟩ since πω = ε.
For each v ∈ VG, there exists no dart d ∈ DG such that both d and α(d) belong
to Ψ(v) since πω is the identity. Thus, forgetting the direction of each dart in Ψ(v), we
obtain the closed trail ψ(v) ⊆ EG. Letting W := { ψ(v) | v ∈ VG }, we have a surjection
ψ : VG → W .
We will prove ψ is injective. Assume that there exist distinct vertices u, v such that
ψ(u) = ψ(v). Let ω′ = (f1, . . . , fr) be the induced order of ω on ψ(u). Since πω′(u) = u,
the edges f1 and fr are incident to u. Also, f1 and fr are incident to v by the same reason.
Hence f1 and fr are parallel edges between u and v. This contradicts that G is simple.
Therefore ψ is injective and hence bijective.
By the definition of maps Ψ and ψ, every v ∈ VG belongs to ψ(v). Moreover,∑
v∈VG
|ψ(v)| =
∑
v∈VG
|Ψ(v)| = |DG| = 2m.
For any e ∈ EG, the two darts on e belongs distinct orbits Ψ(u) and Ψ(v). Then e belongs
to ψ(u) and ψ(v) and the other trails do not contain e. Thus the map ψ : VG → C has the
desired properties.
Example 4.2. For the complete graph K4 in Figure 5, the following map ψ satisfies the
conditions in Proposition 4.1.
ψ(1) = {e1, e4, e5}, ψ(2) = {e1, e3, e6}, ψ(3) = {e2, e4, e6}, ψ(4) = {e2, e3, e5}.
S. Tsujie and R. Uchiumi: Upper embeddability of graphs and products of transpositions . . . 9
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
v11
v12
Figure 6: A counterexample for Eden’s question.
Eden asked whether the necessary conditions in Proposition 4.1 are also sufficient. We
will give a counterexample for this question. Let G be the graph on 12 vertices with 20
edges pictured in Figure 6. Define a map ψ by
ψ(v1) = v1v2v10v1, ψ(v2) = v2v9v10v2, ψ(v3) = v3v10v4v3,
ψ(v4) = v4v10v11v4, ψ(v5) = v5v6v12v5, ψ(v6) = v6v9v12v6,
ψ(v7) = v7v8v12v7, ψ(v8) = v8v11v12v8, ψ(v9) = v9v2v1v10v9,
ψ(v10) = v10v3v4v11v10, ψ(v11) = v11v8v7v12v11, ψ(v12) = v12v5v6v9v12.
The conditions in Proposition 4.1 are satisfied. Suppose thatG has an identity permuta-
tion ordering ω. By Lemma 3.2 there exists a 2-cell embedding ι with fι = |DG/⟨ϕω⟩| =
|VG| = 12 faces. Then the genus gι satisfies
2− 2gι = |VG| − |EG|+ fι = 12− 20 + 12 = 4.
Therefore gι = −1, which is a contradiction.
Problem 4.3. Characterize graphs that have an identity permutation ordering.
ORCID iDs
Shuhei Tsujie https://orcid.org/0000-0001-5805-910X
Ryo Uchiumi https://orcid.org/0000-0002-4956-7177
References
[1] J. Dénes, The representation of a permutation as the product of a minimal number of transpo-
sitions, and its connection with the theory of graphs, Publ. Math. Inst. Hungar. Acad. Sci. 4
(1959), 63–71.
[2] M. Eden, On a relation between labeled graphs and permutations, J. Comb. Theory 2
(1967), 129–134, doi:10.1016/S0021-9800(67)80093-0, https://doi.org/10.1016/
S0021-9800(67)80093-0.
[3] A. M. Foley, J. Kazdan, L. Kröll, S. M. Alberga, O. Melnyk and A. Tenenbaum, Trans-
planting trees: Chromatic symmetric function results through the group algebra of Sn, 2021,
arXiv:2112.09937 [math.CO].
10 Ars Math. Contemp. 25 (2025) #P2.05
[4] Y. Huang and Y. Liu, Face size and the maximum genus of a graph. I. Simple graphs, J. Comb.
Theory Ser. B 80 (2000), 356–370, doi:10.1006/jctb.2000.1990, https://doi.org/10.
1006/jctb.2000.1990.
[5] M. Jungerman, A characterization of upper-embeddable graphs, Trans. Amer. Math. Soc. 241
(1978), 401–406, doi:10.2307/1998852, https://doi.org/10.2307/1998852.
[6] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Studies in the Mathematical
Sciences, Johns Hopkins University Press, Baltimore, MD, 2001.
[7] P. Moszkowski, A solution to a problem of Dénes: a bijection between trees and factorizations
of cyclic permutations, European J. Comb. 10 (1989), 13–16, doi:10.1016/S0195-6698(89)
80028-9, https://doi.org/10.1016/S0195-6698(89)80028-9.
[8] L. Nebeský, Every connected, locally connected graph is upper embeddable, J. Graph Theory
5 (1981), 205–207, doi:10.1002/jgt.3190050211, https://doi.org/10.1002/jgt.
3190050211.
[9] L. Nebeský, A note on upper embeddable graphs, Czechoslovak Math. J. 33 (1983), 37–40, doi:
10.21136/CMJ.1983.101853, https://doi.org/10.21136/CMJ.1983.101853.
[10] L. Nebeský, On locally quasiconnected graphs and their upper embeddability, Czechoslovak
Math. J. 35 (1985), 162–166, doi:10.21136/CMJ.1985.102005, https://doi.org/10.
21136/CMJ.1985.102005.
[11] B. Pawlowski, Chromatic symmetric functions via the group algebra of Sn, Algebr. Comb. 5
(2022), 1–20, doi:10.5802/alco.134, https://doi.org/10.5802/alco.134.
[12] C. Payan and N. H. Xuong, Upper embeddability and connectivity of graphs, Discrete Math.
27 (1979), 71–80, doi:10.1016/0012-365X(79)90070-0, https://doi.org/10.1016/
0012-365X(79)90070-0.
[13] M. Škoviera, The maximum genus of graphs of diameter two, Discrete Math. 87
(1991), 175–180, doi:10.1016/0012-365X(91)90046-5, https://doi.org/10.1016/
0012-365X(91)90046-5.
[14] M. Škoviera, The decay number and the maximum genus of a graph, Math. Slovaca 42 (1992),
391–406.
[15] M. Škoviera and R. Nedela, The maximum genus of vertex-transitive graphs, Discrete Math. 78
(1989), 179–186, doi:10.1016/0012-365X(89)90175-1, https://doi.org/10.1016/
0012-365X(89)90175-1.
[16] R. Uchiumi, Signed graphs and signed cycles of hyperoctahedral groups, Electron. J. Graph
Theory Appl. 11 (2023), 419–429, doi:10.5614/ejgta.2023.11.2.7, https://doi.org/10.
5614/ejgta.2023.11.2.7.
[17] N. H. Xuong, How to determine the maximum genus of a graph, J. Comb. Theory Ser. B
26 (1979), 217–225, doi:10.1016/0095-8956(79)90058-3, https://doi.org/10.1016/
0095-8956(79)90058-3.
[18] N. H. Xuong, Upper-embeddable graphs and related topics, J. Comb. Theory Ser. B 26
(1979), 226–232, doi:10.1016/0095-8956(79)90059-5, https://doi.org/10.1016/
0095-8956(79)90059-5.