ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P3.09 / 505–517
https://doi.org/10.26493/1855-3974.2603.376
(Also available at http://amc-journal.eu)
Partial-dual Euler-genus distributions
for bouquets with small Euler genus*
Yan Yang †
School of Mathematics, Tianjin University, Tianjin, China
Xiaoya Zha
Department of Mathematical Sciences, Middle Tennessee State University,
Murfreesboro, USA
Received 13 April 2021, accepted 22 December 2021, published online 9 June 2022
Abstract
For an arbitrary ribbon graph G, the partial-dual Euler-genus polynomial of G is a gen-
erating function that enumerates partial duals of G by Euler genus. When G is an orientable
ribbon graph, the partial-dual orientable genus polynomial of G is a generating function that
enumerates partial duals of G by orientable genus. Gross, Mansour, and Tucker inaugu-
rated these partial-dual Euler-genus and orientable genus distribution problems in 2020. A
bouquet is a one-vertex ribbon graph. Given a ribbon graph G, its partial-dual Euler-genus
polynomial is the same as that of some bouquet; this motivates our focus on bouquets. We
obtain the partial-dual Euler-genus polynomials for all the bouquets with Euler genus at
most two.
Keywords: Ribbon graph, partial dual, Euler-genus polynomial, orientable genus polynomial.
Math. Subj. Class. (2020): 05C10, 05C30, 05C31, 57M15
1 Introduction
Ribbon graphs are well-known to be equivalent to 2-cell embeddings of graphs. Let G be a
ribbon graph, V (G) and E(G) denote its vertex-disk set and edge-ribbon (or simply ribbon)
set, respectively. In 2009, Chmutov [1] defined the partial dual of G when he was studying
signed Bollobás–Riordan polynomials. For any A ⊆ E(G), the partial dual ribbon graph
with respect to A is denoted by GA. As a generalization of the geometric duality, partial
*The authors would like to thank the anonymous referees for their careful reading and helpful comments.
†Corresponding author. Supported by NNSF of China under Grant NSFC-11971346.
E-mail addresses: yanyang@tju.edu.cn (Yan Yang), xzha@mtsu.edu, xiaoyazha@yahoo.com (Xiaoya Zha)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
506 Ars Math. Contemp. 22 (2022) #P3.09 / 505–517
duality has developed into a topic of independent interest for its applications in graph theory
and topology. The reader is referred to [1, 3] for more background about ribbon graphs and
partial duals.
Given a ribbon graph G, there are 2|E(G)| partial duals of G in total, the problem of
the enumeration of its partial duals GA according to their Euler-genus ε(GA) or orientable
genus γ(GA) was inaugurated by Gross, Mansour, and Tucker [5] in 2020. They defined
the partial-dual Euler-genus (and orientable genus) polynomial of a ribbon graph G, which
was motivated by the Euler-genus (and orientable genus) polynomial [4] of a graph.
Definition 1.1 ([5]). The partial-dual Euler-genus polynomial of a ribbon graph G is the
generating function
∂εG(z) =
∑
A⊆E(G)
zε(G
A)
that enumerates partial duals by Euler genus. The partial-dual orientable genus polynomial
of a ribbon graph G is the generating function
∂γG(z) =
∑
A⊆E(G)
zγ(G
A)
that enumerates partial duals by orientable genus.
In [5], the authors discussed some properties of each polynomial, gave a recursion for
subdivision of an edge, and obtained the partial-dual Euler-genus (or orientable genus)
polynomials for some infinite families of ribbon graphs. In [8], Yan and Jin found some
bouquets having a non-constant partial-dual orientable genus polynomial with only one
non-zero coefficient, which disproved one of conjectures provided in [5], they also ob-
tained the partial-dual Euler-genus polynomials for all bouquets with the number of loops
at most 3 and the partial-dual orientable genus polynomials for all bouquets with the num-
ber of loops at most 4. They also found two infinite families of counterexamples to another
conjecture provided in [5] about the interpolating property of partial-dual Euler-genus poly-
nomials of non-orientable ribbon graphs in [10]. Then Chmutov and Vignes-Tourneret [2]
and Yan and Jin [9] proved that the family of counterexamples given in [8] are the only
counterexamples for that conjecture, independently.
A bouquet is a one-vertex ribbon graph, we denote the bouquet with n loops by Bn. The
bouquets with orientable genus 0 and 1 are called plane bouquets and toroidal bouquets,
respectively; the bouquets with nonorientable genus 1 and 2 are called projective planar
bouquets and Klein bottle bouquets, respectively. In this paper we focus on the partial-
dual Euler-genus polynomial for these bouquets. The following two lemmas motivate our
interest in bouquets.
Lemma 1.2 ([8]). If G is a ribbon graph and A ⊆ E(G), then ∂εG(z) = ∂εGA(z). When
G is orientable, ∂γG(z) = ∂γGA(z).
Lemma 1.3 ([3, 5]). If A is a spanning tree for G, then the partial dual GA has only one
vertex.
From Lemmas 1.2 and 1.3, given a ribbon graph G, its partial-dual Euler-genus poly-
nomial and partial-dual orientable genus polynomial when G is orientable will be the same
as that of some bouquet. From this point of view, for the partial-dual Euler-genus (and
orientable genus) distribution problems, we only need to focus on bouquets.
Y. Yang and X. Zha: Partial-dual Euler-genus distributions for bouquets with small . . . 507
Given a bouquet Bn, we label each loop by distinct letter. By reading these letters we
meet when travelling around the boundary of the vertex-disk of Bn, we obtain a cyclic
order of 2n letters, call it the rotation of Bn. A loop in Bn is called a twisted loop if its
neighbourhood is homeomorphic to a Möbius band, and untwisted loop if its neighbour-
hood is homeomorphic to an annulus. To distinguish between untwisted loops and twisted
loops, we give the same signs + to the two same letters which correspond to a common
untwisted loop, and give two different signs (one +, the other −) to the two same letters
which correspond to a common twisted loop. For simplicity, we usually omit the sign +.
We call the cyclic order of 2n signed letters the signed rotation of Bn. It is easy to check
that there is a 1-to-1 correspondence between the signed rotations and bouquets.
Two loops a and b in a bouquet are interlaced if the rotation of this bouquet is of form
a · · · b · · · a · · · b · · · , otherwise parallel. A loop e in a bouquet is trivial if e is untwisted
and not interlaced with any other loops; otherwise nontrivial. Notice that, all the twisted
loops are nontrivial in this paper, which is different with that in [8] (where a loop in a
bouquet is trivial if it is not interlaced with any other loops, so both trivial untwisted loops
and trivial twisted loops may exist). An essential bouquet is a bouquet whose loops are all
nontrivial. A ribbon graph H is a ribbon subgraph of G if H can be obtained by deleting
vertices and ribbons of G. Given a bouquet B, by deleting all trivial loops, we obtain
an essential bouquet B′ which is a ribbon subgraph of B, and we call B′ the maximum
essential subgraph of B.
The join of two disjoint ribbon graphs G1 and G2, denoted by G1 ∨ G2, is a ribbon
graph which can be obtained by the following way. Firstly we choose an arc p1 on the
boundary of a vertex-disk of G1 that lies between two consecutive ribbon ends, and choose
another such arc p2 on the boundary of a vertex-disk of G2. Next by identifying the arcs
p1 and p2, we merge the two vertex-disks from G1 and G2 into one new vertex-disk, the
ribbon graph obtained is the graph G1∨G2. For the partial-dual Euler-genus polynomial of
the graph G1 ∨G2, the following result had been obtained by Gross, Mansour, and Tucker.
Lemma 1.4 ([5]). If G1 and G2 are disjoint ribbon graphs, then
∂εG1∨G2(z) =
∂εG1(z) · ∂εG2(z).
For a bouquet, it can be obtained by the join of its maximum essential subgraph with
each trivial loops successively. From Lemma 1.4, the following result can be deduced.
Lemma 1.5 ([8]). Let G be a bouquet and G′ be the maximum essential subgraph of G. If
|E(G)| − |E(G′)| = i, then
∂εG(z) = 2
i · ∂εG′(z).
From Lemma 1.5, we can reduce the problem of partial-dual Euler-genus polynomial
of a bouquet to that of its maximum essential subgraph. We also note that the Euler genus
of a bouquet is equal to that of its maximum essential subgraph, due to the additivity of
Euler genus over the join operation.
If A ⊆ E(G), the induced ribbon subgraph G|A is a ribbon subgraph of G whose
ribbon set is A and whose the vertex-disk set consists of all ends of ribbons in A. We use
Ac := E(G) \ A to denote the complement of A ⊆ E(G). By the following lemma, the
Euler genus of a partial dual of a bouquet can be computed from the Euler genus of its two
ribbon subgraphs.
508 Ars Math. Contemp. 22 (2022) #P3.09 / 505–517
Lemma 1.6 ([5]). If G is a bouquet and A ⊆ E(G), then
ε(GA) = ε(G|A) + ε(G|AC ).
We note that ε(G) = 2γ(G) for orientable ribbon graphs, the following two lemmas
can be deduced easily.
Lemma 1.7 ([5]). If G is an orientable bouquet and A ⊆ E(G), then
γ(GA) = γ(G|A) + γ(G|AC ).
Lemma 1.8 ([5]). If G is an orientable ribbon graph, then ∂γG(z) = ∂εG(z2).
In this paper we deduce the forms of the signed rotations of maximum essential sub-
graphs for all projective planar bouquets, Klein bottle bouquets, plane bouquets, and toroidal
bouquets, respectively, and obtain the partial-dual Euler-genus polynomials for these bou-
quets.
2 Partial-dual Euler-genus polynomials of projective planar bouquets
and Klein bottle bouquets
Recall that a ribbon graph is equivalent to a 2-cell embedding of a graph. From the Propo-
sition 4.1.5 in [6], we get the following fact easily.
Lemma 2.1 ([6]). If H is a subgraph of a ribbon graph G, then ε(H) ≤ ε(G).
Lemma 2.2. The bouquet Bn is a plane bouquet if and only if all of its loops are trivial.
Proof. This lemma follows from the definition of trivial loops in Bn.
Lemma 2.3. For a nonorientable bouquet Bn,
(i) if there exists a pair of parallel twisted loops, then ε(Bn) ≥ 2;
(ii) if there exists a pair of interlaced loops, in which one is twisted and the other one is
untwisted, then ε(Bn) ≥ 2;
(iii) if there exists a pair of interlaced untwisted loops, then ε(Bn) ≥ 3.
Proof. For (i) and (ii), the bouquet Bn has ribbon subgraphs B2 and B′2, as shown in
Figure 1(a) and (b), respectively. It is easy to check that ε(B2) = ε(B′2) = 2, then ε(Bn) ≥
2 by Lemma 2.1.
For (iii), there exists a ribbon subgraph with three ribbons e1, e2 and e3 in which e1 and
e2 are interlaced untwisted loops and e3 is a twisted loop (for any nonorientable bouquet,
a twisted loop must exist). The loop e3 can be interlaced with the other i (0 ≤ i ≤ 2)
loops in this ribbon subgraph, by a case analysis, there are three nonequivalent such ribbon
subgraphs B3, B′3 and B
′′
3 , as shown in Figure 1(c)-(e). One can check that ε(B3) =
ε(B′3) = ε(B
′′
3 ) = 3, then ε(Bn) ≥ 3 follows from Lemma 2.1.
The following is easy to prove by induction and simple facial walk counting. We present
it as a technical lemma for the convenience of our later proof. It in fact reveals some
important differences between twisted and untwisted loops in a bouquet.
Y. Yang and X. Zha: Partial-dual Euler-genus distributions for bouquets with small . . . 509
(a) B2 (b) B
′
2 (c) B3
(d) B′3 (e) B
′′
3 (f) B
′′′
3
Figure 1: Some bouquets.
Lemma 2.4. If G is a bouquet and A ⊆ E(G), then
(i) If A (AC , respectively) consists of k untwisted and pairwise parallel loops, then
ε(G|A) = 0 (ε(G|AC ) = 0, respectively);
(ii) If A (AC , respectively) consists of k twisted and pairwise parallel loops, then
ε(G|A) = k (ε(G|AC ) = k, respectively);
(iii) If A (AC , respectively) consists of k twisted and pairwise interlaced loops, then
ε(G|A) = 1 (ε(G|AC ) = 1, respectively).
We first consider the partial-dual Euler-genus polynomials for projective planar bou-
quets.
Lemma 2.5. If Bn is a projective planar bouquet and Bk is the maximum essential sub-
graph of Bn, then the signed rotation of Bk has the form
a1 . . . ak(−a1) . . . (−ak), (1 ≤ k ≤ n). (1)
Proof. Firstly a bouquet with signed rotation (1) has Euler genus 1, from Lemma 2.4(iii).
From items (ii) and (iii) in Lemma 2.3, all the untwisted loops in Bn are trivial loops, so all
the loops in Bk are twisted loops. From item (i) in Lemma 2.3, any pair of twisted loops
in Bk cannot be paralleled to each other, so its signed rotation must have the form (1). The
lemma follows.
Lemma 2.6. If G is a bouquet with the signed rotation a1 . . . at(−a1) . . . (−at), then
∂εG(z) = 2z + (2
t − 2)z2.
Proof. Let X ⊆ E(G) and x = |X|. When x = 0 or x = t, ε(GX) = ε(G) = 1.
When 0 < x < t, the signed rotations of both G|X and G|XC have the form (1), then
510 Ars Math. Contemp. 22 (2022) #P3.09 / 505–517
ε(G|X) = ε(G|XC ) = 1. By Lemma 1.6, ε(GX) = 2. Since there are
(
t
x
)
ways to choose
the x edges,
∂εG(z) = 2z +
t−1∑
x=1
(
t
x
)
z2 = 2z + (2t − 2)z2.
Theorem 2.7. If Bn is a projective planar bouquet with k (1 ≤ k ≤ n) twisted loops, then
∂εBn(z) = 2
n−k(2z + (2k − 2)z2).
Proof. From Lemma 2.5, the k twisted loops induce the maximum essential subgraph of
Bn whose signed rotation has form (1). Combining it with Lemmas 1.5 and 2.6, the theo-
rem follows.
We now consider the partial-dual Euler-genus polynomials for Klein bottle bouquets.
Firstly, we deduce the form of the signed rotation of maximum essential subgraphs for
Klein bottle bouquets. We use the model of disk sum of two projective planes for the Klein
bottle. The fundamental group of Klein bottle is generated by two topologically disjoint
orientation reversing loops a and b (called twisted in this paper). There are three non-
separating loops a, b and d up to homeomorphism, where d = ab is orientation preserving
(called untwisted in this paper).
Lemma 2.8. If Bn is a Klein bottle bouquet and Bk is the maximum essential subgraph of
Bn, then the signed rotation of Bk has the form
a1 . . . aid1 . . . dq(−a1) . . . (−ai)b1 . . . bjdq . . . d1(−b1) . . . (−bj) (2)
in which k = i+ j + q; and
(i) i, j, q ≥ 1, or
(ii) i, j ≥ 1 and q = 0, or
(iii) i, q ≥ 1 and j = 0, or
(iv) j, q ≥ 1 and i = 0.
Proof. It is routine check that the bouquet whose signed rotation with form (2) has Euler
genus two. Notice that Case (iii) and Case (iv) are symmetric and we only need to consider
Case (iii). We have the following observations:
(α): From Lemma 2.4(ii), there are no three twisted loops that are paralleled to each other,
otherwise the Euler genus of Bk is at least three. And there is no subgraph B′′′3 as shown in
Figure 1(f), because ε(B′′′3 ) = 3. Let B
′
k be the ribbon subgraph induced by all the twisted
loops in Bk, the signed rotation of B′k is of form
a1 . . . ai(−a1) . . . (−ai)b1 . . . bj(−b1) . . . (−bj),
in which i+ j ≥ 1.
(β): From Lemma 2.3(iii), there exist no pairs of interlaced untwisted loops in a Klein
bottle bouquet. Each untwisted loop must be interlaced with some twisted loops, otherwise
the untwisted loop is trivial.
(γ): Each nontrivial and untwisted loop must be interlaced with all twisted loops, other-
wise there exits a ribbon subgraph B̂ whose signed rotation is dad(−a)b(−b), and ε(B̂) =
3.
Combining observations (α), (β), and (γ), the lemma follows.
Y. Yang and X. Zha: Partial-dual Euler-genus distributions for bouquets with small . . . 511
According to the four cases listed in Lemma 2.8, the signed rotation of Bk (the maxi-
mum essential subgraph of a Klein bottle bouquet) has one of the following three forms,
a1 . . . ai(−a1) . . . (−ai)b1 . . . bj(−b1) . . . (−bj), (3)
a1 . . . aid1 . . . dq(−a1) . . . (−ai)dq . . . d1, (4)
a1 . . . aid1 . . . dq(−a1) . . . (−ai)b1 . . . bjdq . . . d1(−b1) . . . (−bj) (5)
in which k = i+ j, i, j ≥ 1 in form (3); k = i+ q, i, q ≥ 1 in form (4); and k = i+ j+ q,
i, j, q ≥ 1 in form (5).
Next we compute the partial-dual Euler-genus polynomials for bouquets whose signed
rotation has form (3), (4) and (5) respectively. Let A = {a1, . . . , at}, B = {b1, . . . ,
bm}, D = {d1, . . . , ds}, X ⊆ E(G) and x = |X|.
Lemma 2.9. If G is a bouquet with the signed rotation
a1 . . . at(−a1) . . . (−at)b1 . . . bm(−b1) . . . (−bm), (t,m ≥ 1),
then
∂εG(z) = 4z
2 + 2(2t + 2m − 4)z3 + (2t − 2)(2m − 2)z4.
Proof. Let Bt and Bm be projective planar bouquets whose signed rotation have forms
a1 . . . at(−a1) . . . (−at) and b1 . . . bm(−b1) . . . (−bm), respectively. Then we have G =
Bt ∨Bm. From Lemmas 1.4 and 2.6, the result follows.
Lemma 2.10. If G is a bouquet with the signed rotation
a1 . . . atd1 . . . ds(−a1) . . . (−at)ds . . . d1, (t, s ≥ 1),
then
∂εG(z) = 2z + 2(2
s − 1)z2 + 2(2t − 2)z3 + (2t − 2)(2s − 2)z4.
Proof. When x = 0 or t + s, ε(GX) = ε(G) = 2. When 0 < x < t + s, we have the
following three cases.
Case 1: Assume X ⊆ A. If X = A, then X consists of t twisted and pairwise interlaced
loops and XC consists of s untwisted and pairwise parallel loops. From Lemma 2.4, we
have ε(G|X) = 1 and ε(G|XC ) = 0. Then from Lemma 1.6, we have ε(GX) = 1.
If X ⊂ A, then the signed rotations of the induced ribbon subgraphs G|X and G|XC
have form (1) and (4) respectively, so we have ε(G|X) = 1, ε(G|XC ) = 2 and ε(GX) = 3.
There are
∑t−1
x=1
(
t
x
)
= 2t− 2 ways to choose the x edges. Hence in this case, we have one
partial dual with Euler genus one, and 2t − 2 partial duals with Euler genus three.
Case 2: Assume X ⊆ D. The argument is similar to that for Case 1, by using Lemmas 2.4,
2.8 and 1.6, we get ε(G|X), ε(G|XC ), and ε(GX). Then we calculate the number of ways
to choose the x edges, as shown in Table 1.
Table 1: Euler genus distribution in Case 2.
X ε(G|X) ε(G|XC ) ε(GX) number
X = D 0 1 1 1
X ⊂ D 0 2 2 2s − 2
512 Ars Math. Contemp. 22 (2022) #P3.09 / 505–517
Table 2: Euler genus distribution in Case 3.
X ε(G|X) ε(G|XC ) ε(GX) number
A ⊂ X and D ̸⊂ X 2 0 2 2s − 2
D ⊂ X and A ̸⊂ X 2 1 3 2t − 2
A ̸⊂ X and D ̸⊂ X 2 2 4 (2t − 2)(2s − 2)
Case 3: Assume X ∩ A ̸= ∅ and X ∩ D ̸= ∅. We discuss three subcases as shown in
Table 2, in which we use Lemmas 2.4, 2.5 and 2.8 to compute ε(G|X) and ε(G|XC ).
Summarizing the above, we have ∂εG(z) = 2z + 2(2s − 1)z2 + 2(2t − 2)z3 +
(2t − 2)(2s − 2)z4.
Lemma 2.11. If G is a bouquet with the signed rotation
a1 . . . atd1 . . . ds(−a1) . . . (−at)b1 . . . bmds . . . d1(−b1) . . . (−bm), (t,m, s ≥ 1),
then
∂εG(z) = 2
s+1z2 + (2t+1 + 2m+1 − 4)z3 + (2t+m+s − 2t+1 − 2m+1 − 2s+1 + 4)z4.
Proof. We consider the Euler genus of GX with the following three cases.
Case 1: Ribbons in X come from one of the three ribbon sets A, B and D. We discuss two
subcases as shown in Table 3. And notice that, subcase X ⊆ D includes X = ∅.
Table 3: Euler genus distribution in Case 1.
X ε(G|X) ε(G|XC ) ε(GX) number
X ⊆ D 0 2 2 2s
X ̸= ∅; and X ⊆ A or X ⊆ B 1 2 3 2t + 2m − 2
Case 2: Ribbons in X come from two of the three ribbon sets A, B and D. We discuss
three subcases: X ⊆ A∪B, X ⊆ A∪D and X ⊆ B∪D respectively, as shown in Table 4.
Table 4: Euler genus distribution in Case 2.
X ε(G|X) ε(G|XC ) ε(GX) number
X = A ∪B 2 0 2 1
X ⊂ A ∪B 2 2 4 (2t − 1)(2m − 1)− 1
X = A ∪D or X = B ∪D 2 1 3 2
X ⊂ A ∪D or X ⊂ B ∪D 2 2 4 (2t − 1)(2s − 1) + (2m − 1)(2s − 1)− 2
Case 3: Ribbons in X come from all of three ribbon sets A, B and D. We discuss three
subcases as shown in Table 5. Notice that, subcase XC ⊂ D includes XC = ∅. And when
ribbons in XC come from at least two of A, B and D, the signed rotations of both G|X
Y. Yang and X. Zha: Partial-dual Euler-genus distributions for bouquets with small . . . 513
and G|XC have form (2), thus ε(GX) = ε(G|X) + ε(G|XC ) = 2 + 2 = 4. There are
t−1∑
x=1
(
t
x
)m−1∑
x=1
(
m
x
) s−1∑
x=1
(
s
x
)
+
m−1∑
x=1
(
m
x
) s−1∑
x=1
(
s
x
)
+
t−1∑
x=1
(
t
x
) s−1∑
x=1
(
s
x
)
+
t−1∑
x=1
(
t
x
)m−1∑
x=1
(
m
x
)
= (2t − 2)(2m − 2)(2s − 2) + (2m − 2)(2s − 2)
+ (2t − 2)(2s − 2) + (2t − 2)(2m − 2)
= 2t+m+s − 2t+m − 2t+s − 2m+s + 4
ways to choose X .
Table 5: Euler genus distribution in Case 3.
X ε(G|X) ε(G|XC ) ε(GX) number
XC ⊂ D 2 0 2 2s − 1
XC ̸= ∅;
and XC ⊆ A or XC ⊆ B 2 1 3 2
t + 2m − 4
Ribbons in XC come from
at least two of A, B and D
2 2 4 2t+m+s − 2t+m − 2t+s − 2m+s + 4
Summarizing the above, we have
∂εG(z) = (2
s + 1 + 2s − 1)z2 + (2t + 2m − 2 + 2 + 2t + 2m − 4)z3
+ ((2t − 1)(2m − 1) + (2t − 1)(2s − 1) + (2m − 1)(2s − 1)− 3
+ 2t+m+s − 2t+m − 2t+s − 2m+s + 4)z4
= 2s+1z2 + (2t+1 + 2m+1 − 4)z3
+ (2t+m+s − 2t+1 − 2m+1 − 2s+1 + 4)z4.
From Lemmas 1.5, 2.9, 2.10 and 2.11 the following three theorems can be deduced.
Theorem 2.12. If Bn is a Klein bottle bouquet and the signed rotation of its maximum
essential subgraph is of form a1 . . . ai(−a1) . . . (−ai)b1 . . . bj(−b1) . . . (−bj), (i, j ≥ 1),
then
∂εBn(z) = 2
n−i−j(4z2 + 2(2i + 2j − 4)z3 + (2i − 2)(2j − 2)z4).
Theorem 2.13. If Bn is a Klein bottle bouquet and the signed rotation of its maximum
essential subgraph is of form a1 . . . aid1 . . . dq(−a1) . . . (−ai)dq . . . d1, (i, q ≥ 1), then
∂εBn(z) = 2
n−i−q(2z + 2(2q − 1)z2 + 2(2i − 2)z3 + (2i − 2)(2q − 2)z4).
Theorem 2.14. If Bn is a Klein bottle bouquet and the signed rotation of its maximum
essential subgraph is of form
a1 . . . aid1 . . . dq(−a1) . . . (−ai)b1 . . . bjdq . . . d1(−b1) . . . (−bj), (i, j, q ≥ 1),
then
∂εBn(z) = 2
n−i−j−q(2q+1z2+(2i+1+2j+1−4)z3+(2i+j+q−2i+1−2j+1−2q+1+4)z4).
514 Ars Math. Contemp. 22 (2022) #P3.09 / 505–517
3 Partial-dual orientable genus polynomials of plane bouquets and
toroidal bouquets
In this section, we will deduce the partial-dual orientable genus polynomials of plane bou-
quets and toroidal bouquets, then their partial-dual Euler-genus polynomials follow.
Theorem 3.1. If Bn is a plane bouquet, then ∂γBn(z) = ∂εBn(z) = 2n.
Proof. From Lemma 2.2, the maximum essential subgraph of any plane bouquet is a bou-
quet with no loop. Combining it with Lemmas 1.5 and 1.8, the theorem follows.
For toroidal bouquets, in order to obtain the signed rotation of their maximum essential
subgraphs, we will use the structure of the maximal nonhomotopic loop system of the torus.
Assume x is a point on surface S. A nonhomotopic loop system, denoted by L = {li : i =
1, . . . , t}, is a collection of nonocontractible loops with base point x such that li and lj only
intersect at x and are not homotopic to each other for 1 ≤ i < j ≤ t. A nonhomotopic
loop system L is maximal if adding any noncontractible loop l with x as the base point to
L then l will either be homotopic to some loop li in L or intersect li at some point other
than x. Let ρ(S) = max{|L|}, where L is a maximal nonhomotopic loop system of S, |L|
is the number of loops in L, and the maximality is taken over all such system of S. For the
torus, the following result can be found in both [6] (in Chapter 4) and [7].
Lemma 3.2 ([6, 7]). If S1 is the torus, then ρ(S1) = 3.
Lemma 3.3. If Bn is a toroidal bouquet, then all the nontrivial loops can be partitioned
into at least two homotopy classes and at most three homotopy classes. Furthermore, any
pair of nonhomotopic nontrivial loops interlace mutually.
Proof. For Bn, viewing it as an embedding of one-vertex graph on torus, all the nontrivial
loops are nonocontractible and all the trivial loops are contractible. By Lemma 3.2 all
the nontrivial loops of Bn can be partitioned into at most three homotopy classes. The
fundamental group of torus is Z ⊕ Z, generated by two elements which are not homotopic
and intersect each other transversely, so all the nontrivial loops of Bn can be partitioned
into at least two homotopy classes. On the torus, two nontrivial loops are homotopic if and
only if they are homotopically disjoint. Therefore any pair of nonhomotopic and nontrivial
loops interlace mutually.
Lemma 3.4. If Bn is a toroidal bouquet, then the signed rotation of its maximum essential
subgraph has the form
a1 . . . aib1 . . . bjd1 . . . dqai . . . a1bj . . . b1dq . . . d1, (6)
in which i, j ≥ 1, q ≥ 0 and i+ j + q ≤ n.
Proof. From Lemma 3.3, loops in the maximum essential subgraph are partitioned into
two or three homotopy classes, the loops in the same homotopy class are paralleled with
each other, and loops from different homotopy classes are interlaced with each other, the
theorem follows.
In the following, we will discuss the partial dual distributions of toroidal bouquets in
two cases depending on whether q = 0 or not in Lemma 3.4.
Y. Yang and X. Zha: Partial-dual Euler-genus distributions for bouquets with small . . . 515
Lemma 3.5. If G is a bouquet with the signed rotation
a1 . . . atb1 . . . bmat . . . a1bm . . . b1, (t,m ≥ 1), (7)
then
∂γG(z) = 2 + 2(2
t + 2m − 3)z + (2t − 2)(2m − 2)z2.
Proof. When x = 0 or t + m, γ(GX) = γ(G) = 1. When 0 < x < t + m, we have
the following three cases as shown in Table 6, in which we get γ(G|X), γ(G|XC ) by
Lemmas 2.4 and 3.4, and get γ(GX) by Lemma 1.7.
Table 6: Orientable genus distribution when 0 < x < t+m.
X γ(G|X) γ(G|XC ) γ(GX) number
X = A or X = B 0 0 0 2
X ⊂ A, or X ⊂ B,
or XC ⊂ A, or XC ⊂ B 0 1 1
2
t−1∑
x=1
(
t
x
)
+ 2
m−1∑
x=1
(
m
x
)
= 2(2t + 2m − 4)
X ∩A ̸= ∅, X ∩B ̸= ∅,
XC ∩A ̸= ∅, and XC ∩B ̸= ∅ 1 1 2
t−1∑
x=1
(
t
x
)m−1∑
x=1
(
m
x
)
= (2t − 2)(2m − 2)
Summarizing the above, we have ∂γG(z) = 2 + 2(2t + 2m − 3)z +
(2t − 2)(2m − 2)z2.
Lemma 3.6. If G is a bouquet with the signed rotation
a1 . . . atb1 . . . bmd1 . . . dsat . . . a1bm . . . b1ds . . . d1, (t,m, s ≥ 1), (8)
then
∂γG(z) = 2(2
t + 2m + 2s − 2)z + (2t+m+s − 2t+1 − 2m+1 − 2s+1 + 4)z2.
Proof. We will consider the orientable genus of GX into the following three cases.
Case 1: Ribbons in X come from one of the three ribbon sets A, B and D.
Case 2: Ribbons in X come from two of the three ribbon sets A, B and D.
In this case, we could only consider that ribbons in X come from both A and B, by sym-
metry. Then we have the following two subcases, i.e.,
Subcase 2a: X = A ∪B and Subcase 2b: X ̸= A ∪B.
Case 3: Ribbons in X come from all of the three ribbon sets A, B and D.
In this case, we have the following two subcase, i.e.,
Subcase 3a: XC ⊂ A, or B, or D and Subcase 3b: Otherwise.
In each case, we discuss γ(G|X), γ(G|XC ) and γ(GX), and compute the number of ways
to choose X , as shown in Table 7.
Notice that, in Case 1, because the case X = ∅ has been counted three times in the
three summations, we subtract 2 from the counting. So we have 2t + 2m + 2s − 2 partial
duals with orientable genus one in this case. In Case 2, by symmetry, we have three partial
duals with orientable genus one and
(2t − 1)(2m − 1)− 1 + (2t − 1)(2s − 1)− 1 + (2m − 1)(2s − 1)− 1
= 2t+m + 2m+s + 2t+s − 2t+1 − 2m+1 − 2s+1
516 Ars Math. Contemp. 22 (2022) #P3.09 / 505–517
Table 7: Some orientable genus distribution of GX .
X γ(G|X) γ(G|XC ) γ(GX) number
Case 1 0 1 1
t∑
x=0
(
t
x
)
+
m∑
x=0
(
m
x
)
+
s∑
x=0
(
s
x
)
− 2
= 2t + 2m + 2s − 2
Subcase 2a 1 0 1 1
Subcase 2b 1 1 2
t∑
x=1
(
t
x
) m∑
x=1
(
m
x
)
− 1
= (2t − 1)(2m − 1)− 1
Subcase 3a 1 0 1
t−1∑
x=1
(
t
x
)
+
m−1∑
x=1
(
m
x
)
+
s−1∑
x=1
(
s
x
)
+ 1
= 2t + 2m + 2s − 5
Subcase 3b 1 1 2 2t+m+s − 2t+m − 2t+s − 2m+s + 4
partial duals with orientable genus two. In Subcase 3a, notice that, we haven’t include
XC = ∅ in any of the three summations, so we add one to the counting. In Subcase 3b,
there are
t−1∑
x=1
(
t
x
)m−1∑
x=1
(
m
x
) s−1∑
x=1
(
s
x
)
+
m−1∑
x=1
(
m
x
) s−1∑
x=1
(
s
x
)
+
t−1∑
x=1
(
t
x
) s−1∑
x=1
(
s
x
)
+
t−1∑
x=1
(
t
x
)m−1∑
x=1
(
m
x
)
= (2t − 2)(2m − 2)(2s − 2) + (2m − 2)(2s − 2)
+ (2t − 2)(2s − 2) + (2t − 2)(2m − 2)
= 2t+m+s − 2t+m − 2t+s − 2m+s + 4
ways to choose the x edges. Hence, in Case 3, we have 2t +2m +2s − 5 partial duals with
orientable genus one and 2t+m+s − 2t+m − 2t+s − 2m+s +4 partial duals with orientable
genus two.
Summarizing the above, we have
∂γG(z) = (2
t + 2m + 2s − 2 + 3 + 2t + 2m + 2s − 5)z
+ (2t+m + 2m+s + 2t+s − 2t+1 − 2m+1
− 2s+1 + 2t+m+s − 2t+m − 2t+s − 2m+s + 4)z2
= 2(2t + 2m + 2s − 2)z + (2t+m+s − 2t+1 − 2m+1 − 2s+1 + 4)z2.
From Lemmas 1.5, 1.8, 3.5 and 3.6, the following two theorems can be deduced.
Theorem 3.7. If Bn is a toroidal bouquet and the signed rotation of its maximum essential
subgraph has the form a1 . . . aib1 . . . bjai . . . a1bj . . . b1 in which i, j ≥ 1 and i + j ≤ n,
then
∂γBn(z) = 2
n−i−j(2 + 2(2i + 2j − 3)z + (2i − 2)(2j − 2)z2),
and
∂εBn(z) = 2
n−i−j(2 + 2(2i + 2j − 3)z2 + (2i − 2)(2j − 2)z4).
Y. Yang and X. Zha: Partial-dual Euler-genus distributions for bouquets with small . . . 517
Theorem 3.8. If Bn is a toroidal bouquet and the signed rotation of its maximum es-
sential subgraph has the form a1 . . . aib1 . . . bjd1 . . . dqai . . . a1bj . . . b1dq . . . d1, in which
i, j, q ≥ 1 and i+ j + q ≤ n, then
∂γBn(z) = 2
n−i−j−q(2(2i + 2j + 2q − 2)z + (2i+j+q − 2i+1 − 2j+1 − 2q+1 + 4)z2),
and
∂εBn(z) = 2
n−i−j−q(2(2i + 2j + 2q − 2)z2 + (2i+j+q − 2i+1 − 2j+1 − 2q+1 + 4)z4).
ORCID iDs
Yan Yang https://orcid.org/0000-0002-9666-5167
Xiaoya Zha https://orcid.org/0000-0003-1940-7428
References
[1] S. Chmutov, Generalized duality for graphs on surfaces and the signed Bollobás-Riordan poly-
nomial, J. Comb. Theory, Ser. B 99 (2009), 617–638, doi:10.1016/j.jctb.2008.09.007.
[2] S. Chmutov and F. Vignes-Tourneret, On a conjecture of Gross, Mansour and Tucker, Eur. J.
Comb. 97 (2021), 7, doi:10.1016/j.ejc.2021.103368, id/No 103368.
[3] J. A. Ellis-Monaghan and I. Moffatt, Graphs on Surfaces. Dualities, Polynomials, and Knots,
SpringerBriefs Math., Springer, New York, NY, 2013, doi:10.1007/978-1-4614-6971-1.
[4] J. L. Gross and M. L. Furst, Hierarchy for imbedding-distribution invariants of a graph, J.
Graph Theory 11 (1987), 205–220, doi:10.1002/jgt.3190110211.
[5] J. L. Gross, T. Mansour and T. W. Tucker, Partial duality for ribbon graphs. I: Distributions,
Eur. J. Comb. 86 (2020), 20, doi:10.1016/j.ejc.2020.103084, id/No 103084.
[6] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore,
MD, 2001, https://www.sfu.ca/˜mohar/Book.html.
[7] B. Xu and X. Zha, Thickness and outerthickness for embedded graphs, Discrete Math. 341
(2018), 1688–1695, doi:10.1016/j.disc.2018.02.024.
[8] Q. Yan and X. Jin, Counterexamples to a conjecture by Gross, Mansour and Tucker on partial-
dual genus polynomials of ribbon graphs, Eur. J. Comb. 93 (2021), 13, doi:10.1016/j.ejc.2020.
103285, id/No 103285.
[9] Q. Yan and X. Jin, Partial-dual genus polynomials and signed intersection graphs, 2021,
arXiv:2102.01823v1 [math.CO].
[10] Q. Yan and X. Jin, Counterexamples to the interpolating conjecture on partial-dual genus poly-
nomials of ribbon graphs, Eur. J. Comb. 102 (2022), 7, doi:10.1016/j.ejc.2021.103493, id/No
103493.