Partial-dual Euler-genus polynomials for two classes of bouquets

Abstract

[European J. Combin., 2020, 86: Paper No. 103084, 20 pp.] introduced the concept of partial-dual Euler-genus polynomial in the ribbon graphs and gave the interpolation conjecture. That is, the partial-dual Euler-genus polynomial for any non-orientable ribbon graph is interpolating. In fact, [European J. Combin., 2022, 102: Paper No. 103493, 7 pp.] gave two classes of counterexamples to deny the conjecture, and only one or two of the side loops contained in the two classes of bouquets were non-orientable. On the basis of [European J. Combin., 2022, 102: Paper No. 103493, 7 pp.], we further calculate the partial-dual Euler-genus polynomials of two other classes of bouquets. One is non-interpolating, whose side loop has an arbitrary number of non-orientable loops. The other is interpolating, whose side loop has an arbitrary number of both non-orientable loops and orientable loops.

Graphical abstract

Keywords

Ribbon graph / partial-dual / genus / polynomial / interpolating

1 Introduction

In 2002, Bollobás and Riordan [1] first introduced the concept of ribbon graph. A ribbon graph was essentially a bounded surface with a graph structure, which was equivalent to cellularly embedded graph [5]. Geometric duality is a relatively old concept that has been widely applied in various fields such as geometry. In 2009, Chmutov [3] extended the geometric duality of cellularly embedded graph to partial duality. The geometric duality of ribbon graph preserves the genus of the ribbon graph while partial duality cannot. At the same time, partial duality has critical theoretical significance and research value in various fields. Therefore, this research direction has attracted the attention of many experts and scholars as one of the research hotspots in recent years, as shown in [4, 9].

In 2020, Gross et al. [6] first proposed the concept of partial-dual Euler-genus polynomials of ribbon graph, i.e., the generating function of ribbon graph with respect to all partial-dual Euler genuses. This paper not only uses recursive methods to explore the four classes of partial-dual Euler genus polynomials with ribbon graph and log-concavity, but also provides multiple conjectures, which are currently the main research hotspots, as shown in [2, 7]. Gross et al. [6] proved that the partial-dual orientable genus polynomials of all orientable ribbon graphs are interpolating polynomials. For non-orientable ribbon graphs, a similar interpolation conjecture is given.

Conjecture 1.1 [6] (Interpolation Conjecture)　 The partial-dual Euler genus polynomial of any non-orientable ribbon graph is an interpolating polynomial.

Recently, Yan and Jin [11] presented two classes of counterexamples to prove that the interpolation conjecture was incorrect. These two classes of bouquets contained only one or two non-orientable side loops. This paper follows their approach and further calculates the partial-dual Euler-genus polynomials of the two classes of bouquets. The first type is non-interpolating, and its side loops have an arbitrary number of non-orientable loops, which is an extension of the counterexample [11]; the second type is interpolating, and its side loops have an arbitrary number of orientable and non-orientable loops.

2 Preliminaries

Definition 2.1 [1]　Ribbon graph G=(V(G),E(G)) is a bounded surface with a graph structure (which may be non-orientable), which is the union of two sets of closed disks: one is the set of vertex disks V\left(G\right); the other is the set of edge disks E\left(G\right), and the following conditions are satisfied.

(1) The intersection of vertex disk and edge disk at a disjoint line segment is called a common line segment;

(2) Each common line segment is exactly located on the boundary between a vertex disk and edge disk;

(3) Each edge disk contains exactly two common line segments.

Let G be a ribbon graph, and v\in V\left(G\right), e\in E\left(G\right). By removing common line segments on the boundary of vertex v, we obtain several disjoint line segments, each of which is called the vertex line segment of v. By deleting the common line segments on the boundary of e, two disjoint line segments are obtained, which are called the edge line segments of e, as shown in Fig.1.

The boundary branch of ribbon graph G is a set of cycles composed of its own vertex and edge segments, where the number of cycles is the number of boundary branches, denoted byf\left(G\right). Fig.2 provides an example of a ribbon graph with 2 boundary branches.

Assume G=(V(G), E\left(G\right)) is a ribbon graph and A\subseteq E\left(G\right). If geometric duality transformation is only applied to the edge subset A of G, that is, every boundary branch of the generated ribbon graph(V(G),A) of G is bonded to a disk and all vertices of the disk inside G are deleted. So, the resulting ribbon graph is called the partial duality of G with respect to G, denoted as G^A. For a detailed introduction to the partial duality of ribbon graph, see [3, 5]. If G is orientable as a bounded surface, then G is orientable.

Definition 2.2 [4]　The Euler characteristic \chi \left(G\right) of ribbon graph G is defined as follows:

\chi \left(G\right)=v\left(G\right)-e\left(G\right)+f\left(G\right)=2k\left(G\right)-\epsilon \left(G\right),

where v\left(G\right), e\left(G\right), and k\left(G\right) represent the number of vertex, edge, and connected component of ribbon graph G, respectively, and \epsilon \left(G\right) indicate the Euler genus of G as bounded surface.

A ribbon graph B with a vertex number of 1 is called a bouquet. Obviously, all edges of bouquet B exist in the form of loops, and any edge derived subgraph of the bouquet remains a bouquet. If A\subseteq E\left(B\right), we still use A to represent the edge derived subgraph of B, and A^c to represent the edge derived subgraph of B with respect to the complement A^c of A. A loop in the bouquet is called non-orientable. If the bounded surface formed by this loop and the vertex of the bouquet is homeomorphic to the Möbius band, otherwise it is called orientable. A loop in the bouquet is called trivial if there are no other loops alternating with it.

Signed rotation of bouquet B is a cyclic ordering of the signed half-edges at the only vertex. If loop e is orientable, then we assign two half-edge signs + (or -); if loop e is non-orientable, then we assign one half-edge sign + and another half-edge sign-.

Assume B is a bouquet, a,b\in E\left(B\right), and A, P, and Q are three strings in the signed rotation of B, then the following four basic operations will not change the number of boundary branches of the bouquet [8].

Operation 2.1　Transform the signed rotation from PaQAa to PaAQa, denoted by

PaQAa\stackrel{\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}2.1}{\to }PaAQa.

Operation 2.2　Transform the signed rotation from PaQb(-a) to P(-b)aQ(-a), denoted by

PaQb(-a)\stackrel{\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}2.2}{\to }P(-b)aQ(-a).

Operation 2.3　Transform the signed rotation from Pabab to P, denoted by

Pabab\stackrel{\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}2.3}{\to }P.

Operation 2.4　Transform the signed rotation from Pa(-a) to P, denoted by

Pa(-a)\stackrel{\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}2.4}{\to }P.

The above four operations are closely related to the standardization of polygon representation of closed surfaces. Operations 2.1 and 2.2 correspond to the inverse and sequential operations of closed surface standardization, respectively. Operations 2.3 and 2.4 correspond to the delete operation of closed surface standardization, as detailed in [10].

Definition 2.3 [6]　The partial-dual Euler-genus polynomial of ribbon graph G is generating function

{}^{\mathrm{\partial }}{\epsilon }_G\left(z\right):=\sum _{A\subseteq E\left(G\right)} z^{\epsilon \left(G^A\right)},

which calculates all partial-dual Euler genuses of G.

Definition 2.4 [12]　The intersection graph of bouquet B is denoted as I\left(B\right), and its vertex set corresponds to E\left(B\right), where the two vertices e and f in I\left(B\right) are adjacent if and only if the cyclic ordering of half-edges at the only vertex in B appears in the form of e\cdots f\cdots e\cdots f\cdots. The signed intersection graph of B is denoted as SI\left(B\right), which is obtained by adding a positive or negative sign at each vertex of I\left(B\right). If the loop e is orientable, the vertex e of I\left(B\right) is assigned a positive sign, otherwise the vertex e of I\left(B\right) is assigned a negative sign.

For the sake of convenience, we often round off the positive signs in the signed rotation or signed intersection graph. Fig.3 shows a bouquet and its corresponding signed intersection graph.

Lemma 2.1 [12]　 If bouquets B₁ and B₂ have the same signed intersection graph, then \epsilon \left(B_1\right)=\epsilon \left(B_2\right).

Lemma 2.2 [12]　 Assume B is a bouquet, then Euler genus ε(B) is given by the following equation:

\epsilon \left(B\right)=1+e\left(B\right)-f\left(B\right).

Lemma 2.3 [6]　 If B is a bouquet, then

\epsilon \left(B^A\right)=\epsilon \left(A\right)+\epsilon \left(A^c\right).

3 First class of bouquet

For any n\ge 1, the signed rotation of bouquet C_{2n+a} is

\left(1^{\prime },2^{\prime },3^{\prime },\dots ,a^{\prime },1,2,\dots ,2n-1,2n,-a^{\prime },\dots ,-3^{\prime },-2^{\prime },-1^{\prime },2n-1,2n,\dots ,1,2\right),

which shows that there are a total of a non-orientable loops (denoted as 1^{\prime },2^{\prime },3^{\prime },\dots ,a^{\prime }, respectively) and 2n orientable loops (denoted as 1,2,\dots ,2n-1,2n, respectively), where any non-orientable loop intersects with any orientable loop, and for any 1\le i\le n, loops 2i-1 and 2i intersect with each other, as shown in Fig.4. Assume A\subseteq E\left(C_{2n+a}\right) and 1\le i\le n. If \{2i-1,2i\}\subseteq A, then we say \{2i-1,2i\} is a pair of double ribbons in A. If 2i-1\in A but 2i\notin A (or 2i\in A but 2i-1\notin A), then we say 2i-1 (or 2i) is a single ribbon in A.

Lemma 3.1　 Assume A\subseteq E\left(C_{2n+a}\right) and s\left(A\right)is the number of single ribbons in A. If A does not contain 1^{\prime },2^{\prime },\dots ,a^{\prime }, then

f\left(A\right)=s\left(A\right)+1.

Proof　If the maximum labeled edge of A appears as double ribbons, that is A=(P,2i-1,2i,2i-1,2i,Q), then

f\left(A\right)=f\left(P,2i-1,2i,2i-1,2i,Q\right)=f\left(P,Q\right).

If the maximum labeled edge of A appears as single ribbons, that is A=(P,2i,2i,Q) or A=(P,2i-1,2i-1,Q), then

f\left(A\right)=f(P,2i,2i,Q)=f(P,Q)+1.

By repeating the above operations, we can get f\left(A\right)=s\left(A\right)+1. □

Lemma 3.2　 Assume A\subseteq E\left(C_{2n+a}\right), 1^{\prime },2^{\prime },\dots ,a^{\prime }\in A, and s\left(A\right) is the number of single ribbons of A.

f\left(A\right)=\{\begin{array}{ll}1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right),& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0\mathrm{a}\mathrm{n}\mathrm{d}ais\mathrm{a}\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{d}\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r};\\ s\left(A\right)+1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0\mathrm{a}\mathrm{n}\mathrm{d}ais\mathrm{a}\mathrm{n}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}.\end{array}

Proof　Case 1: Except for ribbons 1^{\prime },2^{\prime },\dots ,a^{\prime } in A, the minimum labeled edge is single ribbon, that is

A=\left(1^{\prime },2^{\prime },\dots ,a^{\prime },2j,P,-a^{\prime },\dots ,-2^{\prime },-1^{\prime },Q,2j\right),

or

A=(1^{\prime },2^{\prime },\dots ,a^{\prime },2j-1,P,-a^{\prime },\dots ,-2^{\prime },-1^{\prime },Q,2j-1).

Then there is

\begin{array}{rl}f\left(A\right)=& f(1^{\prime },2^{\prime },\dots ,a^{\prime },2j,P,-a^{\prime },\dots ,-2^{\prime },-1^{\prime },Q,2j)\\ & \frac{\text{Operation}\text{2}\text{.1}}{a=2j,A=P}f(1^{\prime },2^{\prime },\dots ,a^{\prime },2j,-a^{\prime },\dots ,-2^{\prime },-1^{\prime },Q,P,2j)\\ =& f(Q,P)+f(2j,1^{\prime },2^{\prime },\dots ,a^{\prime },2j,-a^{\prime },\dots ,-2^{\prime },-1^{\prime })-1,\end{array}

and

\begin{array}{rl}f(2j,& 1^{\prime },2^{\prime },\dots ,a^{\prime },2j,-a^{\prime },\dots ,-2^{\prime },-1^{\prime })\\ & \underset{a=1^{\prime },b=2j}{\stackrel{\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}2.2}{\to }}f\left(1^{\prime },2^{\prime },\dots ,a^{\prime },2j,-a^{\prime },\dots ,-2^{\prime },-2j,-1^{\prime }\right)\\ & \underset{a=2^{\prime },b=-2j}{\stackrel{\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}2.2}{\to }}f\left(1^{\prime },2^{\prime },2j,3^{\prime },\dots ,a^{\prime },2j,-a^{\prime },\dots ,-3^{\prime },-2^{\prime },-1^{\prime }\right)\\ & \underset{a=1^{\prime }}{\stackrel{\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}2.4}{\to }}f\left(2^{\prime },2j,3^{\prime },\dots ,a^{\prime },2j,-a^{\prime },\dots ,-3^{\prime },-2^{\prime }\right)\\ & \underset{a=2^{\prime }}{\stackrel{\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}2.4}{\to }}f\left(2j,3^{\prime },\dots ,a^{\prime },2j,-a^{\prime },\dots ,-3^{\prime }\right).\end{array}

By repeating the above operations, when a is an odd number,

f(2j,1^{\prime },2^{\prime },\dots ,a^{\prime },2j,-a^{\prime },\dots ,-2^{\prime },-1^{\prime })=f(2j,a^{\prime },2j,-a^{\prime })=1.

So

\begin{array}{rl}f\left(A\right)& =f(P,Q)+f(2j,1^{\prime },2^{\prime },\dots ,a^{\prime },2j,-a^{\prime },\dots ,-2^{\prime },-1^{\prime })-1\\ & =f(P,Q)+1-1=f(P,Q).\end{array}

Since 1^{\prime },\dots ,a^{\prime }\notin (P,Q), it can be seen from Lemma 3.1 that f(P,Q)=s(P,Q)+1 and s(P,Q)=s\left(A\right)-1. We have

f\left(A\right)=f(P,Q)=s(P,Q)+1=s\left(A\right)-1+1=s\left(A\right).

When a is an even number,

f(2j,1^{\prime },2^{\prime },\dots ,a^{\prime },2j,-a^{\prime },\dots ,-2^{\prime },-1^{\prime })=f(2j,2j)=2.

Since then,

\begin{array}{rl}f\left(A\right)& =f(P,Q)+f(2j,1^{\prime },2^{\prime },\dots ,a^{\prime },2j,-a^{\prime },\dots ,-2^{\prime },-1^{\prime })-1\\ & =f(P,Q)+2-1=f(P,Q)+1=s(P,Q)+1+1\\ & =s\left(A\right)-1+1+1=s\left(A\right)+1.\end{array}

Case 2: Except for ribbons 1^{\prime },2^{\prime },\dots ,a^{\prime } in A, the minimum labeled edge is double ribbons, that is

A=\left(1^{\prime },2^{\prime },\dots ,a^{\prime },2j-1,2j,P,-a^{\prime },\dots ,-2^{\prime },-1^{\prime },Q,2j-1,2j\right).

We have

\begin{array}{rl}f\left(A\right)=& f\left(1^{\prime },2^{\prime },\dots ,a^{\prime },2j-1,2j,P,-a^{\prime },\dots ,-2^{\prime },-1^{\prime },Q,2j-1,2j\right)\\ & \frac{\text{Operation}2.1}{a=2j-1,A=1^{\prime },2^{\prime },\dots ,a^{\prime }}f(2j-1,2j,P,-a^{\prime },\dots ,-2^{\prime },-1^{\prime },Q,2j-1,1^{\prime },2^{\prime },\dots ,a^{\prime },2j)\\ & \frac{\text{Operation}2.1}{a=2j,A=1^{\prime },2^{\prime },\dots ,a^{\prime }}f(2j-1,2j,1^{\prime },2^{\prime },\dots ,a^{\prime },P,-a^{\prime },\dots ,-2^{\prime },-1^{\prime },Q,2j-1,2j)\\ & \frac{\text{Operation}2.3}{a=2j-1,b=2j}f(1^{\prime },2^{\prime },\dots ,a^{\prime },P,-a^{\prime },\dots ,-2^{\prime },-1^{\prime },Q).\end{array}

Ifs\left(A\right)=0, then

\begin{array}{rl}f\left(A\right)& =f(1^{\prime },2^{\prime },\dots ,a^{\prime },P,-a^{\prime },\dots ,-2^{\prime },-1^{\prime },Q)\\ & =\cdots =f(1^{\prime },2^{\prime },\dots ,a^{\prime },-a^{\prime },\dots ,-2^{\prime },-1^{\prime })=1;\end{array}

If s\left(A\right)>0, repeat the above operations, and cut down when encountering double ribbons or return to Case 1 when encountering single ribbons. That is when a is an odd number, f\left(A\right)=s\left(A\right); when a is an even number, f\left(A\right)=s\left(A\right)+1.

Combining Case 1 and Case 2, we get

f\left(A\right)=\{\begin{array}{ll}1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right),& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0\mathrm{a}\mathrm{n}\mathrm{d}a\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{d}\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r};\\ s\left(A\right)+1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0\mathrm{a}\mathrm{n}\mathrm{d}a\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{n}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}.\end{array}

Q.E.D. □

Definition 3.1　For arbitrary non-negative integer n, the splitting of n refers to writing it as a combination of (n_1,n_2), where n_1, n_2 are both non-negative integers, and n_1+n_2=n. If n_1, n_2 are both non-zero integers, then (n_1,n_2) is called a non-zero combination; if (n_1,n_2) are both even numbers, then (n_1,n_2) is called an (even, even) combination. Similarly, define (odd, even), (even, odd), and (odd, odd) combinations.

Lemma 3.3　 Assume A\subseteq E\left(C_{2n+a}\right), then

(1) when a is an odd number,

\epsilon \left(C_{2n+a}^A\right)=\{\begin{array}{ll}2n+a,& s\left(A\right)=0;\\ 2n-2s\left(A\right)+a+1,& s\left(A\right)>0.\end{array}

(2) when a is an even number,

\epsilon \left(C_{2n+a}^A\right)=\{\begin{array}{ll}2n+a,& s\left(A\right)=0;\\ 2n-2s\left(A\right)+a+2,& s\left(A\right)>0\text{and}a\text{is (odd, odd)};\\ 2n-2s\left(A\right)+a,& s\left(A\right)>0\text{and}a\text{is (even, even)}.\end{array}

Proof　According to Definition 3.1, a can be split into a combination of (a_1,a_2). Without loss of generality, let combination (a_1,a_2) represent a₁ edges falling into A and a₂ edges falling into A^cin 1^{\prime },2^{\prime },\dots ,a^{\prime }. With Lemma 3.2, when a₁ is an odd number,

f\left(A\right)=\{\begin{array}{ll}1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right),& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

When a₁ is an even number,

f\left(A\right)=\{\begin{array}{ll}1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right)+1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

(1) When a is an odd number, (a_1,a_2) only has two types of combinations, namely (odd, even) and (even, odd).

Case 1: (odd, even) combination. Now

f\left(A\right)+f\left(A^c\right)=\{\begin{array}{ll}1+1=2,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right)+\left(s\right(A)+1)=2s\left(A\right)+1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

Case 2: (even, odd) combination. Now

f\left(A\right)+f\left(A^c\right)=\{\begin{array}{ll}1+1=2,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ \left(s\right(A)+1)+s\left(A\right)=2s\left(A\right)+1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

That is, the (odd, even) and (even, odd) combinations have no effect upon Euler genus.

\begin{array}{rl}\epsilon \left(C_{2n+a}^A\right)& =\left|A\right|+\left|A^c\right|-f\left(A\right)-f\left(A^c\right)+2\\ & =\{\begin{array}{ll}2n+a-2+2=2n+a,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ 2n+a-\left(2s\right(A)+1)+2=2n-2s\left(A\right)+a+1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}\end{array}

(2) When a is an even number, (a_1,a_2) only has two types of combinations, namely (even,even) and (odd, odd).

Case 1: (even, even) combination. Now

f\left(A\right)+f\left(A^c\right)=\{\begin{array}{ll}1+1=2,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ \left(s\right(A)+1)+\left(s\right(A)+1)=2s\left(A\right)+2,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

Case 2: (odd, odd) combination. Now

f\left(A\right)+f\left(A^c\right)=\{\begin{array}{ll}1+1=2,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right)+s\left(A\right)=2s\left(A\right),& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

The effect of (even, even) and (odd, odd) combinations on Euler genus whens\left(A\right)>0 slightly varies, and the Euler genus remains the same when s\left(A\right)=0, i.e.,

\begin{array}{rl}\epsilon \left(C_{2n+a}^A\right)& =\left|A\right|+\left|A^c\right|-f\left(A\right)-f\left(A^c\right)+2\\ & =\{\begin{array}{ll}2n+a,& s\left(A\right)=0;\\ 2n-2s\left(A\right)+a+2,& s\left(A\right)>0\text{and}a\text{is (odd, odd);}\\ 2n-2s\left(A\right)+a,& s\left(A\right)>0\text{and}a\text{is (even, even)}.\end{array}\end{array}

Q.E.D. □

Theorem 3.1　 The partial-dual Euler-genus polynomial of bouquet C_2n+ais

(1) when a is an odd number,

{}^{\mathrm{\partial }}{\epsilon }_{C_{2n+a}}\left(z\right)=2^{n+a}{z}^{2n+a}+\sum _{s=1}^n 2^{n+a}\left(\genfrac{}{}{0pt}{}{n}{s}\right)z^{2n-2s+a+1};

(2) when a is an even number,

{}^{\mathrm{\partial }}{\epsilon }_{C_{2n+a}}\left(z\right)=(n+2)\cdot 2^{n+a-1}{z}^{2n+a}+2^{n+a-1}\sum _{s=1}^{n-1} \left[\left(\genfrac{}{}{0pt}{}{n}{s+1}\right)+\left(\genfrac{}{}{0pt}{}{n}{s}\right)\right]z^{2n-2s+a}+2^{n+a-1}{z}^a.

Proof　According to Lemma 3.3, we will discuss the following two cases.

(1) When a is an odd number:

(i) \epsilon \left(C_{2n+a}^A\right)=2n+a if and only if s\left(A\right)=0 and a is split into arbitrary combination (a_1,a_2). The value of a₁ can be 0,1,2,\dots ,a-1,a. And since s\left(A\right)=0, every double ribbon has two options whether to take value or not, so there are 2^n\left[\right(\genfrac{}{}{0pt}{}{a}{0})+(\genfrac{}{}{0pt}{}{a}{1})+\cdots +(\genfrac{}{}{0pt}{}{a}{a}\left)\right]=2^{n+a} possibilities;

(ii) \epsilon \left(C_{2n+a}^A\right)=2n-2s+a+1(1\le s\le n) if and only if s\left(A\right)>0. The value of a₁ can be 0,1,2,\dots ,a. For s single ribbons, there are \left(\genfrac{}{}{0pt}{}{n}{s}\right)2^s possibilities; for the remaining n-s double ribbons, there are 2^{n-s} possibilities, so there are 2^n\left(\genfrac{}{}{0pt}{}{n}{s}\right)\left[\right(\genfrac{}{}{0pt}{}{a}{0})+(\genfrac{}{}{0pt}{}{a}{1})+\cdots +(\genfrac{}{}{0pt}{}{a}{a}\left)\right]=2^{n+a}\left(\genfrac{}{}{0pt}{}{n}{s}\right) possibilities.

(2) When a is an even number:

(i) \epsilon \left(C_{2n+a}^A\right)=2n+a if and only if s\left(A\right)=0 and a is split into arbitrary combination (a_1,a_2). The value of a₁ can be 0,1,2,\dots ,a or s\left(A\right)=1 and a is split into (odd, odd) combination. Whens\left(A\right)=0, every double ribbon has two options whether to take value or not, so there are 2^n\left[\right(\genfrac{}{}{0pt}{}{a}{0})+(\genfrac{}{}{0pt}{}{a}{1})+\cdots +(\genfrac{}{}{0pt}{}{a}{a}\left)\right]=2^{n+a} possibilities; when s(A)=1 and a is split into (odd, odd) combination, the value of a₁ can be 1,3,\dots ,a-1. So there are 2^n\left(\genfrac{}{}{0pt}{}{n}{1}\right)[(\genfrac{}{}{0pt}{}{a}{1})+(\genfrac{}{}{0pt}{}{a}{3})+\cdots +(\genfrac{}{}{0pt}{}{a}{a-1})]=n\cdot 2^{n+a-1} possibilities.

(ii) \epsilon \left(C_{2n+a}^A\right)=2n-2s+a(1\le s\le n-1) if and only if s\left(A\right)=s+1 and a is split into (odd, odd) combination or s\left(A\right)=s and a is split into (even, even) combination. When s\left(A\right)=s+1 and a is split into (odd, odd) combination, the value of a₁ can be 1,3,\dots ,a-1, so there are 2^n\left(\genfrac{}{}{0pt}{}{n}{s+1}\right)\left[\right(\genfrac{}{}{0pt}{}{a}{1})+(\genfrac{}{}{0pt}{}{a}{3})+\cdots +(\genfrac{}{}{0pt}{}{a}{a-1}\left)\right]=\left(\genfrac{}{}{0pt}{}{n}{s+1}\right)2^{n+a-1} possibilities. When s(A)=s and a is split into (even, even) combination, the value of a₁ can be 0,2,\dots ,a, so there are 2^n\left(\genfrac{}{}{0pt}{}{n}{s}\right)[(\genfrac{}{}{0pt}{}{a}{0})+(\genfrac{}{}{0pt}{}{a}{2})+\cdots +(\genfrac{}{}{0pt}{}{a}{a})]=\left(\genfrac{}{}{0pt}{}{n}{s}\right)2^{n+a-1} possibilities.

(iii) \epsilon \left(C_{2n+a}^A\right)=a if and only if s\left(A\right)=n and a is split into (even, even) combination. When s\left(A\right)=n and a is split into (even, even) combination, the value of a₁ can be 0,2,\dots ,a, so there are 2^n\left[\right(\genfrac{}{}{0pt}{}{a}{0})+(\genfrac{}{}{0pt}{}{a}{2})+\cdots +(\genfrac{}{}{0pt}{}{a}{a}\left)\right]=2^{n+a-1} possibilities. □

Note 3.1　When a=1,2, Theorem 3.1 is two types of counterexamples in [11] by Yan and Jin.

4 Second class of bouquet

For any n\ge 1, the signed rotation of bouquet C_{2n+a+b}(a\ge 1,b\ge 1) is

\left(1^{\prime },2^{\prime },\dots ,(a+b{)}^{\prime },1,2,\dots ,2n-1,2n,\pm (a+b{)}^{\prime },\dots ,\pm 2^{\prime },\pm 1^{\prime },2n-1,2n,\dots ,1,2\right).

It represents a total of (a+b) loops on the side edge, denoted as 1^{\prime },2^{\prime },\dots ,(a+b{)}^{\prime }, where there are a orientable loops and b non-orientable loops, in an uncertain order. Because it cannot be determined whether a certain loop is orientable or non-orientable, we represent the other end of each loop with \pm 1^{\prime },\pm 2^{\prime },\dots ,\pm (a+b{)}^{\prime }. Meanwhile, the (a+b) ribbons and all other loops 1,2,\dots ,2n-1,2n intersect with each other. Similarly, for each 1\le i\le n, ribbons 2i-1 and 2i intersect with each other, as shown in Fig.5. Assume A\subseteq E\left(C_{2n+a+b}\right) and 1\le i\le n. If \{2i-1,2i\}\subseteq A, we say \{2i-1,2i\}is a pair of double ribbons. If 2i-1\in A, 2i\notin A(or 2i\in A, 2i-1\notin A), we say 2i-1(or 2i) is a single ribbon of A.

Bouquet D_{a+b}(a\ge 0,b\ge 0) is composed of a trivial orientable loops and b trivial non-orientable loops.

Lemma 4.1　 For the bouquet D_{a+b}(a\ge 0,b\ge 0), the number of boundary branches f\left(D_{a+b}\right)=a+1.

Proof　Due to the fact that the number and position of trivial non-orientable loops have no effect on the number of boundary branches, and for every additional trivial orientable loop (regardless of where it is added), the number of boundary branches increases by 1, so f\left(D_{a+b}\right)=a+1. □

Lemma 4.2　 Assume A\subseteq E\left(C_{2n+a+b}\right), when 1^{\prime },2^{\prime },\dots ,a^{\prime },(a+1{)}^{\prime },\dots ,(a+b{)}^{\prime }\in A,

f\left(A\right)=\{\begin{array}{ll}a+1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right)+a-1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

Proof　Assume

\begin{array}{c}A=\left(1^{\prime },2^{\prime },\dots ,(a+b{)}^{\prime },P,\pm (a+b{)}^{\prime },\dots ,\pm 2^{\prime },\pm 1^{\prime },Q\right),\\ A^{\prime }=\left(\begin{array}{c}{1}^{\prime },\dots ,a^{\prime },(a+1{)}^{\prime },\dots ,(a+b{)}^{\prime },P,-(a+b{)}^{\prime },\dots ,-(a+1{)}^{\prime },a^{\prime },\dots ,1^{\prime },Q\end{array}\right).\end{array}

Obviously, A and A^{\prime } have the same signed intersection graph, and s\left(A\right)=s\left(A^{\prime }\right), so it can be seen from Lemma 2.1 and 2.2 that f\left(A\right)=f\left(A^{\prime }\right). We only need to calculate the number of boundary branches of A^{\prime }.

Case 1: Except for ribbons 1^{\prime },2^{\prime },\dots ,a^{\prime },(a+1{)}^{\prime },\dots ,(a+b{)}^{\prime } in A^{\prime }, the minimum labeled edge is single ribbon. Assume

A^{\prime }=\left(M,x^{\prime },y^{\prime },N,2j,P,N^{\prime },-y^{\prime },x^{\prime },M^{\prime },Q,2j\right),

or

A^{\prime }=(M,x^{\prime },y^{\prime },N,2j-1,P,N^{\prime },-y^{\prime },x^{\prime },M^{\prime },Q,2j-1).

Then

\begin{array}{rl}f\left(A^{\prime }\right)& =f\left(M,x^{\prime },y^{\prime },N,2j,P,N^{\prime },-y^{\prime },x^{\prime },M^{\prime },Q,2j\right)\\ & \frac{\text{Operation}2.1}{a=2j,A=P}f(M,x^{\prime },y^{\prime },N,2j,N^{\prime },-y^{\prime },x^{\prime },M^{\prime },Q,P,2j)\\ & =f(P,Q)+f(2j,M,x^{\prime },y^{\prime },N,2j,N^{\prime },-y^{\prime },x^{\prime },M^{\prime })-1.\end{array}

And

\begin{array}{rl}f(2j,& M,x^{\prime },y^{\prime },N,2j,N^{\prime },-y^{\prime },x^{\prime },M^{\prime })\\ & \frac{\text{Operation2.1}}{a=2j,A=M}f(2j,x^{\prime },y^{\prime },N,M,2j,N^{\prime },-y^{\prime },x^{\prime },M^{\prime })\\ & \frac{\text{Operation}2.1}{a=x^{\prime },A=y^{\prime },N,M}f(2j,x^{\prime },2j,N^{\prime },-y^{\prime },y^{\prime },N,M,x^{\prime },M^{\prime })\\ & \frac{\text{Operation}\text{2.1}}{a=2j,A=N^{\prime },-y^{\prime },y^{\prime },N,M}f(N^{\prime },-y^{\prime },y^{\prime },N,M,2j,x^{\prime },2j,x^{\prime },M^{\prime })\\ & \frac{\text{Operation}\text{2.3}}{a=2j,b=x^{\prime }}f(N^{\prime },-y^{\prime },y^{\prime },N,M,M^{\prime }).\end{array}

From Lemma 4.1, f(N^{\prime },-y^{\prime },y^{\prime },N,M,M^{\prime })=a-1+1=a. And since M,x^{\prime },y^{\prime },N\notin (P,Q), it can be obtained from Lemma 3.1 that f(P,Q)=s(P,Q)+1, and s(P,Q)=s\left(A^{\prime }\right)-1. Hence,

\begin{array}{rl}f\left(A^{\prime }\right)& =f(P,Q)+f(2j,M,x^{\prime },y^{\prime },N,2j,N^{\prime },-y^{\prime },x^{\prime },M^{\prime })-1\\ & =s(P,Q)+1+a-1=s\left(A^{\prime }\right)-1+1+a-1\\ & =s\left(A^{\prime }\right)+a-1=s\left(A\right)+a-1.\end{array}

Case 2: Except for ribbons 1^{\prime },2^{\prime },\dots ,a^{\prime },(a+1{)}^{\prime },\dots ,(a+b{)}^{\prime } in A^{\prime }, the minimum labeled edge is double ribbon. Assume

A^{\prime }=(M,x^{\prime },y^{\prime },N,2j-1,2j,P,N^{\prime },-y^{\prime },x^{\prime },M^{\prime },Q,2j-1,2j).

There exists

\begin{array}{rl}f\left(A^{\prime }\right)=& f(M,x^{\prime },y^{\prime },N,2j-1,2j,P,N^{\prime },-y^{\prime },x^{\prime },M^{\prime },Q,2j-1,2j)\\ & \frac{\text{Operation2.1}}{a=2j-1,A=M,x^{\prime },y^{\prime },N}f(2j-1,2j,P,N^{\prime },-y^{\prime },x^{\prime },M^{\prime },Q,2j-1,M,x^{\prime },y^{\prime },N,\\ & \frac{\text{Operation}\text{2.1}}{a=2j,A=M,x^{\prime },y^{\prime },N}f(2j-1,2j,M,x^{\prime },y^{\prime },N,P,N^{\prime },-y^{\prime },x^{\prime },M^{\prime },Q,2j-1,2j)\\ & \frac{\text{Operation}\text{2.3}}{a=2j-1,b=2j}f(M,x^{\prime },y^{\prime },N,P,N^{\prime },-y^{\prime },x^{\prime },M^{\prime },Q).\end{array}

If s\left(A^{\prime }\right)=0, it can be obtained from Lemma 4.1 that

\begin{array}{rl}f\left(A^{\prime }\right)& =f(M,x^{\prime },y^{\prime },N,P,N^{\prime },-y^{\prime },x^{\prime },M^{\prime },Q)\\ & =\cdots =f(M,x^{\prime },y^{\prime },N,N^{\prime },-y^{\prime },x^{\prime },M^{\prime })\\ & =a+1.\end{array}

If s\left(A^{\prime }\right)>0, repeat the above operations such that the minimum labeled edge is single ribbon, and we can get from Case 1

f\left(A^{\prime }\right)=s\left(A^{\prime }\right)+a-1=s\left(A\right)+a-1.

Q.E.D. □

Lemma 4.3　 Assume A\subseteq E\left(C_{2n+a+b}\right), the Euler genus of C_{2n+a+b}^A is

where j indicates the number of non-orientable loops in A.

Proof　Assume i=\left|\right\{1^{\prime },2^{\prime },\dots ,a^{\prime }\}\cap A|. It can be seen from Definition 2.2 and Lemma 2.3 that

1-\left|A\right|+f\left(A\right)=2-\epsilon \left(A\right),1-\left|A^c\right|+f\left(A^c\right)=2-\epsilon \left(A^c\right).

So \epsilon \left(C_{2n+a+b}^A\right)=\left|A\right|+\left|A^c\right|-f\left(A\right)-f\left(A^c\right)+2.

Case 1: , that is \{1^{\prime },2^{\prime },\dots ,a^{\prime }\}\cap A\ne \varnothing and \{1^{\prime },2^{\prime },\dots ,a^{\prime }\}\cap A^c\ne \varnothing. It can be seen from Lemma 4.2 that

f\left(A\right)=\{\begin{array}{ll}i+1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right)+i-1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

Since the number of orientable and non-orientable loops in A^c is respectively a-i, b-j,

f\left(A^c\right)=\{\begin{array}{ll}a-i+1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right)+a-i-1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

Hence, when s\left(A\right)=0,

\epsilon \left(C_{2n+a+b}^A\right)=2n+a+b-(i+1)-(a-i+1)+2=2n+b;

when s\left(A\right)>0,

\epsilon \left(C_{2n+a+b}^A\right)=2n+a+b-\left(s\right(A)+i-1)-\left(s\right(A)+a-i-1)+2=2n-2s\left(A\right)+b+4.

Case 2: If 1^{\prime },2^{\prime },\dots ,a^{\prime }\in A or A^c, that is all orientable loops are in A or A^c. Without loss of generality, let 1^{\prime },2^{\prime },\dots ,a^{\prime }\in A. We can get from Lemma 4.2 that

f\left(A\right)=\{\begin{array}{ll}a+1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right)+a-1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

Furthermore, there are b-j non-orientable ribbons in A^c, so it can be seen from Lemma 3.2 that when b-j is odd,

f\left(A^c\right)=\{\begin{array}{ll}1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right),& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

When b-j is even,

f\left(A^c\right)=\{\begin{array}{ll}1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)=0;\\ s\left(A\right)+1,& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}s\left(A\right)>0.\end{array}

Hence, if s\left(A\right)=0, then

\epsilon \left(C_{2n+a+b}^A\right)=2n+a+b-\left(a+1\right)-1+2=2n+b.

If s\left(A\right)>0 and b-j is odd, then

\epsilon \left(C_{2n+a+b}^A\right)=2n+a+b-\left(s\right(A)+a-1)-s\left(A\right)+2=2n-2s\left(A\right)+b+3.

If s\left(A\right)>0 and b-j is even, then

\epsilon \left(C_{2n+a+b}^A\right)=2n+a+b-\left(s\right(A)+a-1)-\left(s\right(A)+1)+2=2n-2s\left(A\right)+b+2.

Q.E.D. □

Theorem 4.1　 The partial-dual Euler-genus polynomial of bouquet C_{2n+a+b}(a\ge 1,b\ge 1) is given by the following formula:

\begin{array}{rl}{\mathrm{\partial }}_{{\epsilon }_{C_{2n+a+b}}\left(z\right)}=& n\cdot 2^{n+b}(2^a-2)z^{2n+b+2}+2^{n+b}\left[2^a+n+(2^a-2)\frac{n(n-1)}{2}\right]z^{2n+b}\\ & +\sum _{s=1}^n 2^{n+b}\left(\genfrac{}{}{0pt}{}{n}{s}\right)z^{2n-2s+b+3}\\ & +\sum _{s=2}^{n-1} 2^{n+b}\left[\left(\genfrac{}{}{0pt}{}{n}{s}\right)+(2^a-2)\left(\genfrac{}{}{0pt}{}{n}{s+1}\right)\right]z^{2n-2s+b+2}+2^{n+b}{z}^{b+2}.\end{array}

Proof　According to Lemma 4.3, we will discuss the following five cases:

Case 1: \epsilon \left(C_{2n+a+b}^A\right)=2n+b if and only if s\left(A\right)=0; or s\left(A\right)=1 and 1^{\prime },2^{\prime },\dots ,a^{\prime }\in A or A^c, b-j is even or s\left(A\right)=2 and there is at least one orientable ribbon in A, A^c.

(1) When s\left(A\right)=0, there is i(0\le i\le a) orientable ribbons and j(0\le j\le b) non-orientable ribbons in A. And since s\left(A\right)=0, every double ribbon has two options whether to take value or not, so there are 2^n\sum _{i=0}^a \left(\genfrac{}{}{0pt}{}{a}{i}\right)\cdot \sum _{j=0}^b \left(\genfrac{}{}{0pt}{}{b}{j}\right)=2^{n+a+b} possibilities.

(2) When s\left(A\right)=1 and 1^{\prime },2^{\prime },\dots ,a^{\prime }\in A or A^c, b-j is even. Without loss of generality we assume b is even, there are a orientable ribbons and j(0\le j\le b,j takes an even number) non-orientable ribbons in A. And since s\left(A\right)=1, there are \left(\genfrac{}{}{0pt}{}{n}{1}\right)2^1=2 possibilities for this one single ribbon, and there are 2^{n-1} possibilities for the remaining n-1double ribbons. So, there are 2\cdot 2^n\left(\genfrac{}{}{0pt}{}{n}{1}\right)[(\genfrac{}{}{0pt}{}{b}{0})+(\genfrac{}{}{0pt}{}{b}{2})+\cdots +(\genfrac{}{}{0pt}{}{b}{b})]=n\cdot 2^{n+b} possibilities.

(3) When s\left(A\right)=2 and there is at least one orientable ribbon in A, A^c, then there are i(1\le i\le a-1) orientable ribbons and j(0\le j\le b) non-orientable ribbons in A. And since s\left(A\right)=2, there are \left(\genfrac{}{}{0pt}{}{n}{2}\right)2^2 possibilities for the two single ribbons and 2^{n-2} possibilities for the remaining n-2 double ribbons. So, there are 2^n\left(\genfrac{}{}{0pt}{}{n}{2}\right)\left[\right(\genfrac{}{}{0pt}{}{a}{1})+(\genfrac{}{}{0pt}{}{a}{2})+\cdots +(\genfrac{}{}{0pt}{}{a}{a-1}\left)\right]\left[\right(\genfrac{}{}{0pt}{}{b}{0})+(\genfrac{}{}{0pt}{}{b}{1})+\cdots +(\genfrac{}{}{0pt}{}{b}{b}\left)\right]=2^{n+b}(2^a-2)\frac{n(n-1)}{2} possibilities.

Case 2: \epsilon \left(C_{2n+a+b}^A\right)=2n-2s+b+2(2\le s\le n-1) if and only if s\left(A\right)=s and 1^{\prime },2^{\prime },\dots ,a^{\prime }\in A or A^c, b-j is even; or s\left(A\right)=s+1 and there is at least one orientable ribbon in A, A^c.

(1) When s\left(A\right)=s and 1^{\prime },2^{\prime },\dots ,a^{\prime }\in A or A^c, b-jis even. Without loss of generality we assume b is even, there are a orientable ribbons and j(0\le j\le b,jtakes an even number) non-orientable ribbons in A. And since s\left(A\right)=s, there are \left(\genfrac{}{}{0pt}{}{n}{s}\right)2^s possibilities for the s single ribbons, and there are 2^{n-s} possibilities for the remaining n-sdouble ribbons. So, there are 2\cdot 2^n\left(\genfrac{}{}{0pt}{}{n}{s}\right)[(\genfrac{}{}{0pt}{}{b}{0})+(\genfrac{}{}{0pt}{}{b}{2})+\cdots +(\genfrac{}{}{0pt}{}{b}{b})]=\left(\genfrac{}{}{0pt}{}{n}{s}\right)\cdot 2^{n+b} possibilities;

(2) When s\left(A\right)=s+1 and there is at least one orientable ribbon in A, A^c, then there are i(1\le i\le a-1) orientable ribbons and j(0\le j\le b) non-orientable ribbons in A. And since s\left(A\right)=s+1, there are \left(\genfrac{}{}{0pt}{}{n}{s+1}\right)2^{s+1} possibilities for the s+1 single ribbons, and there are 2^{n-(s+1)} possibilities for the remaining n-(s+1) double ribbons. So there are 2^n\left(\genfrac{}{}{0pt}{}{n}{s+1}\right)\left[\right(\genfrac{}{}{0pt}{}{a}{1})+(\genfrac{}{}{0pt}{}{a}{2})+\cdots +(\genfrac{}{}{0pt}{}{a}{a-1}\left)\right]\left[\right(\genfrac{}{}{0pt}{}{b}{0})+(\genfrac{}{}{0pt}{}{b}{1})+\cdots +(\genfrac{}{}{0pt}{}{b}{b}\left)\right]=2^{n+b}(2^a-2)\left(\genfrac{}{}{0pt}{}{n}{s+1}\right) possibilities.

Case 3: \epsilon \left(C_{2n+a+b}^A\right)=b+2 if and only if s\left(A\right)=n and 1^{\prime },2^{\prime },\dots ,a^{\prime }\in A or A^c, b-jis even. Without loss of generality we assume b is even, there are a orientable ribbons and j(0\le j\le b, j takes an even number) non-orientable ribbons in A. And since s\left(A\right)=n, there are \left(\genfrac{}{}{0pt}{}{n}{n}\right)2^n=2^n possibilities for the n single ribbons, and there is one possibility for the remaining n-n=0 double ribbons. So, there are 2\cdot 2^n\left(\genfrac{}{}{0pt}{}{n}{n}\right)\left[\right(\genfrac{}{}{0pt}{}{b}{0})+(\genfrac{}{}{0pt}{}{b}{2})+\cdots +(\genfrac{}{}{0pt}{}{b}{b}\left)\right]=2^{n+b} possibilities.

Case 4: \epsilon \left(C_{2n+a+b}^A\right)=2n-2s+b+3(1\le s\le n) if and only if s\left(A\right)>0 and 1^{\prime },2^{\prime },\dots ,a^{\prime }\in A or A^c, b-jis odd. Without loss of generality we assume b is even and 1^{\prime },2^{\prime },\dots ,a^{\prime }\in A, i.e., there are a orientable ribbons and j(0\le j\le b, j takes an odd number) non-orientable ribbons in A. There are \left(\genfrac{}{}{0pt}{}{n}{s}\right)2^s possibilities for the s single ribbons, and there are 2^{n-s} possibilities for the remaining n-s double ribbons. So, there are 2\cdot 2^n\left[\right(\genfrac{}{}{0pt}{}{b}{1})+(\genfrac{}{}{0pt}{}{b}{3})+\cdots +(\genfrac{}{}{0pt}{}{b}{b-1}\left)\right]\cdot \left(\genfrac{}{}{0pt}{}{n}{s}\right)=2^{n+b}\left(\genfrac{}{}{0pt}{}{n}{s}\right) possibilities.

Case 5: \epsilon \left(C_{2n+a+b}^A\right)=2n+b+2 if and only s\left(A\right)=1 and there is at least one orientable ribbon in A, A^c. Then there are i(1\le i\le a-1) orientable ribbons andj(0\le j\le b) non-orientable ribbons in A. And since s\left(A\right)=1, there are \left(\genfrac{}{}{0pt}{}{n}{1}\right)2^1 possibilities for the one single ribbon, and there are 2^{n-1} possibilities for the remainingn-1 double ribbons. There are 2^n\left(\genfrac{}{}{0pt}{}{n}{1}\right)\left[\right(\genfrac{}{}{0pt}{}{a}{1})+(\genfrac{}{}{0pt}{}{a}{2})+\cdots +(\genfrac{}{}{0pt}{}{a}{a-1}\left)\right]\left[\right(\genfrac{}{}{0pt}{}{b}{0})+(\genfrac{}{}{0pt}{}{b}{1})+\cdots +(\genfrac{}{}{0pt}{}{b}{b}\left)\right]=n\cdot 2^{n+b}(2^a-2) possibilities. □

Note 4.1　The partial-dual Euler-genus polynomial of the second class of bouquets is interpolating.

5 Conclusions

Gross et al. [6, 7] primarily discussed the interpolation properties of partial-dual Euler-genus polynomials of ribbon graph, posed conjectures about interpolation properties, and also calculated partial-dual Euler-genus polynomials for some special classes of ribbon graph. In this paper, based on [11], two types of partial-dual Euler-genus polynomials for bouquets are proposed, one of which is non-interpolating and the other of which is interpolating. The objects of the above discussion and calculation are ribbon graphs with certain special structures. Next, we can try to continuously delve into these ribbon graphs and depict ribbon graphs of partial-dual Euler-genus polynomials with interpolatory properties (or non-interpolatory properties) as much as possible. Tucker presented a report at the Special Session on Topological Perspectives on Graph Theory, Classic and Recent during the virtual Western Sectional Meeting of the 2021 American Mathematical Society, which touched on the odd and even interpolation of partial-dual Euler-genus polynomials of ribbon graphs. Specifically, if there are both odd and even degrees of nonzero terms in partial-dual Euler-genus polynomials of ribbon graphs, then the polynomial is oddly and evenly interpolated. One polynomial is called oddly (or evenly) interpolated, if the odd (or even) degree of the nonzero coefficient term in the polynomial is continuous. There is currently no progress on this problem, but it has raised significant research questions for the study of interpolation properties of partial-dual Euler-genus polynomials of ribbon graphs.

References

[1] Bollobás B. A polynomial of graphs on surfaces. Math Ann 2002; 323(1): 81–96

[2] Chen Q Y, Chen Y C. Parallel edges in ribbon graphs and interpolating behavior of partial-duality polynomials. European J Combin 2022; 102: 103492

[3] Chmutov S. Generalized duality for graphs on surfaces and the signed Bollobás—Riordan polynomial. J Combin Theory Ser B 2009; 99(3): 617–638

[4] Ellis-Monaghan J A, Moffatt I. Twisted duality for embedded graphs. Trans Amer Math Soc 2012; 364(3): 1529–1569

[5] Ellis-MonaghanJ AMoffattI. Graphs on Surfaces: Dualities, Polynomials, and Knots, SpringerBriefs in Mathematics. New York: Springer, 2013

[6] Gross J L, Mansour T, Tucker T W. Partial duality for ribbon graphs, I: distributions. European J Combin 2020; 86: 103084

[7] Gross J L, Mansour T, Tucker T W. Partial duality for ribbon graphs, II: partial-twuality polynomials and monodromy computations. European J Combin 2021; 95: 103329

[8] LivingstonC. Knot Theory, Carus Mathematical Monographs. Vol 24, Washington, DC: Mathematical Association of America, 1993

[9] Moffatt I. A characterization of partially dual graphs. J Graph Theory 2011; 67(3): 198–217

[10] MunkresJ R. Topología, 2nd Ed, Upper Saddle River. NJ: Prentice Hall, 2000 (in Spanish)

[11] Yan Q, Jin X A. Counterexamples to the interpolating conjecture on partial-dual Genus polynomials of ribbon graphs. European J Combin 2022; 102: 103493

[12] Yan Q, Jin X A. Partial-dual polynomials and signed intersection graphs. Forum Math Sigma 2022; 10: e69

RIGHTS & PERMISSIONS

Higher Education Press 2024