1 Introduction
The concept of partial duality was introduced in [Reference Chmutov4] by Chmutov, and together with other partial twualities, it has received ever-increasing attention; their applications span topological graph theory, knot theory, matroids/delta-matroids and physics. We assume readers are familiar with the basic knowledge of topological graph theory; see, for example, [Reference Gross and Tucker16, Reference Mohar and Thomassen22]. For a ribbon graph G and a subset A of its edge-ribbons
$E(G)$
, the partial dual
$G^{A}$
of G with respect to A is a ribbon graph obtained from G by glueing a disc to G along each boundary component of the spanning ribbon subgraph
$(V (G), A)$
(such discs will be the vertex-discs of
$G^{A}$
), removing the interiors of all vertex-discs of G and keeping the edge-ribbons unchanged. For more detailed discussions of the ribbon graphs and partial duals, see [Reference Bollobás and Riordan1, Reference Chmutov4, Reference Deng, Jin and Metsidik9, Reference Ellis-Monaghan and Moffatt11, Reference Metsidik and Jin18].
Similar to the extensively studied polynomial in topological graph theory that enumerates by Euler genus all embeddings of a given graph, in [Reference Gross, Mansour and Tucker14], Gross, Mansour and Tucker introduced the partial-dual polynomials for arbitrary ribbon graphs.
Definition 1.1 (Definition 3.1 of [Reference Gross, Mansour and Tucker14])
The partial-dual polynomial of any ribbon graph G is the generating function
$$ \begin{align*}^{\partial}\varepsilon_{G}(z)=\sum_{A\subseteq E(G)}z^{\varepsilon(G^{A})}\end{align*} $$
that enumerates all partial duals of G by Euler genus.
A bouquet is a ribbon graph with only one vertex. It is observed in [Reference Ellis-Monaghan and Moffatt11, Reference Gross, Mansour and Tucker14] that for any connected ribbon graph G, whenever A is a spanning tree,
$G^{A}$
will be a bouquet. Thus the partial-dual polynomial of any connected ribbon graph is equal to that of a bouquet. Hence we shall restrict ourselves to bouquets.
In [Reference Yan and Jin23], we introduced the notion of signed interlace sequences of bouquets and proved that two bouquets with the same signed interlace sequence have the same partial-dual polynomial if the number of edges of the bouquets is less than 4 and two orientable bouquets with the same signed interlace sequence have the same partial-dual polynomial if the number of edges of the bouquets is less than 5. As we observed in Remarks 13 and 17 in [Reference Yan and Jin23], there are bouquets with the same signed interlace sequence but different partial-dual polynomials. The first purpose of this paper is to strengthen the notion of signed interlace sequences such that it can determine the partial-dual polynomial completely.
Intersection graphs (also called circle graphs) appear and are very useful in both graph theory and combinatorial knot theory [Reference Godsil and Royle12]. For example, a characterisation of those graphs that can be realised as intersection graphs is given by an elegant theorem of Bouchet [Reference Bouchet3]. The signed interlace sequence of a bouquet is the degree sequence (with signs) of its signed intersection graph. Based on a theorem of Chmutov and Lando [Reference Chmutov and Lando6], we shall prove that two bouquets with the same signed intersection graph have the same partial-dual polynomial.
Then we focus on signed intersection graphs; the intersection polynomial is introduced, and a recursion for this polynomial is given and used to compute intersection polynomials of paths and stars. We also prove that the intersection polynomial contains a nonzero constant term: that is, the bouquet has a plane partial dual if and only if the signed intersection graph is positive and bipartite.
In [Reference Gross, Mansour and Tucker14], Gross, Mansour and Tucker characterised connected ribbon graphs with constant polynomials: that is, one of the partial duals is a tree. They also found examples of nonorientable ribbon graphs whose polynomials have only one (nonconstant) term. The second purpose of this paper is to give a characterisation of when all partial duals of a bouquet have the same Euler genus. We will show that the partial-dual polynomial of a prime nonorientable bouquet has only one nonconstant term if and only if its intersection graph is trivial. Chmutov and Vignes-Tourneret [Reference Chmutov and Vignes-Tourneret5] mentioned that this result has also been obtained by Maya Thompson (Royal Holloway University of London). They did not provide a reference, and we have not found any references either. For orientable ribbon graphs, Gross, Mansour and Tucker posed the following conjecture.
Conjecture 1.2 (Conjecture 3.1 of [Reference Gross, Mansour and Tucker14])
There is no orientable ribbon graph having a nonconstant partial-dual polynomial with only one nonzero coefficient.
The conjecture is not true. In [Reference Yan and Jin23], we found an infinite family of counterexamples (see Proposition 6.3) whose intersection graphs are nontrivial complete graphs of odd order. In this paper, we shall prove that Conjecture 1.2 is actually true for all prime orientable bouquets except the family of counterexamples. We point out that this is also obtained independently by Chmutov and Vignes-Tourneret [Reference Chmutov and Vignes-Tourneret5]; their arXiv paper appeared about one week before our arXiv paper, but the proof is not completely the same. They also mentioned our results in their published paper [Reference Chmutov and Vignes-Tourneret5]. We will discuss the similarities and differences of the two proofs in Remark 6.11.
This paper is organised as follows. In Section 2, we recall the notions of signed rotations and signed intersection graphs. In Section 3, we recall the notion of mutant chord diagrams and a theorem of Chmutov and Lando on mutant chord diagrams and intersection graphs. In Section 4, we prove that the signed intersection graph can determine the partial-dual polynomial. In Section 5, we introduce the intersection polynomial and discuss its basic properties. In Section 6, we give a characterisation of when all partial duals of a bouquet have the same Euler genus. In the final section, we pose several problems for further study.
2 Signed rotations and signed intersection graphs
Let e be an edge of a ribbon graph G. If the vertex-discs at the ends of e are distinct, we say that e is proper. If e is a loop at the vertex disc v and
$e\cup v$
is homeomorphic to a Möbius band, then we call e a twisted loop. Otherwise, it is said to be an untwisted loop.
A signed rotation [Reference Gross and Tucker16] of a bouquet is a cyclic ordering of the half-edges at the vertex, and if the edge is an untwisted loop, then we give the same sign
$+$
or
$-$
to the corresponding two half-edges and give the different signs (one
$+$
, the other
$-$
) otherwise. The sign
$+$
is always omitted. See Figure 1 for an example. Sometimes we will use the signed rotation to represent the bouquet itself. Two signed rotations are the same if one can be obtained from the other by a sequence of cyclic permutations or reversals, where a reversal means reversing the cyclic order of the half-edges about the vertex or changing the signs of both labels corresponding to an edge at the same time.
Figure 1 A bouquet with the signed rotation
$(a, c, -a, d, b, d, c, -b)$
and its signed intersection graph.
The intersection graph [Reference Chmutov and Lando6]
$I(B)$
of a bouquet B is the graph with vertex set
$E(B)$
and in which two vertices
$e_{1}$
and
$e_{2}$
of
$I(B)$
are adjacent if and only if their ends are met in the cyclic order
$e_{1}\cdots e_{2}\cdots e_{1}\cdots e_{2}\cdots $
when traveling around the boundary of the unique vertex of B: that is, in the signed rotation of B.
The signed intersection graph
$SI(B)$
of a bouquet B consists of
$I(B)$
and a
$+$
or
$-$
sign at each vertex of
$I(B)$
, where the vertex corresponding to the untwisted loop of B is signed
$+$
, and the vertex corresponding to the twisted loop of B is signed
$-$
. See Figure 1 for an example. A signed intersection graph is said to be positive if each of its vertices is signed
$+$
. The following lemma is obvious.
Lemma 2.1. A bouquet B is orientable if and only if its signed intersection graph
$SI(B)$
is positive.
Remark 2.2. Let
$B_{1}, B_{2}$
and
$B_{3}$
be bouquets with signed rotations
$$ \begin{align*}(a, b, c, f, g, d, f, g, b, d, e, a, e, c),\end{align*} $$
$$ \begin{align*}(a, b, c, f, g, d, f, g, e, d, b, e, a, c),\end{align*} $$
and
$$ \begin{align*}(a, b, g, c, d, e, c, f, e, d, b, f, a, g),\end{align*} $$
respectively. It is easily seen that they have the same signed interlace sequence
$(1, 2, 2, 2, 2, 2, 3)$
. But
$SI(B_{1})=SI(B_{2})\neq SI(B_{3})$
, as shown in Figure 2. Furthermore, we can obtain that
$$ \begin{align*}^{\partial}\varepsilon_{B_{1}}(z)=~^{\partial}\varepsilon_{B_{2}}(z)=48z^{6}+68z^{4}+12z^{2},\end{align*} $$
but
$$ \begin{align*}^{\partial}\varepsilon_{B_{3}}(z)=40z^{6}+64z^{4}+22z^{2}+2.\end{align*} $$
In the following, we shall prove that two bouquets with the same signed intersection graph have the same partial-dual polynomial: that is, signed intersection graphs can determine the partial-dual polynomials completely. In the next section, we will first recall mutants.
Figure 2
$SI(B_{1}), SI(B_{2})$
and
$SI(B_{3})$
, respectively.
3 Mutants
In knot theory, mutants are a pair of knots obtained from one another by rotating a tangle. Mutants are usually very difficult to distinguish by knot polynomials.
A chord diagram refers to a set of chords with distinct endpoints on a circle. A combinatorial analogue of the tangle in mutant knots is a share. A share [Reference Chmutov and Lando6] in a chord diagram is a union of two arcs of the outer circle and chords ending on them possessing the following property: each chord, one of whose ends belongs to these arcs, has both ends on these arcs. A mutation [Reference Chmutov and Lando6] of a chord diagram is another chord diagram obtained by a
$180^{\circ }$
rotation of a share about one of the three axes (i.e., a vertical axis, a horizontal axis and an axis perpendicular to the page). See Figure 3 for an example. Note that the composition of rotations about two of the three axes will be exactly the rotation about the third axis. Two chord diagrams are said to be mutant [Reference Chmutov and Lando6] if they can be transformed into one another by a sequence of mutations.
Figure 3 A share and mutations of a chord diagram along the share.
Theorem 3.1 (Theorem 2 of [Reference Chmutov and Lando6])
Two chord diagrams have the same intersection graph if and only if they are mutant.
For the details, we refer the reader to [Reference Chmutov and Lando6]. Mutations can be defined for bouquets similarly. Suppose
$P=p_{1}p_{2}\cdots p_{k}$
is a string; then
$P^{-1}=p_{k}p_{k-1}\cdots p_{1}$
is called the inverse of P.
Definition 3.2. Let B be a bouquet with signed rotation
$(MPNQ)$
, where both labels of each edge must belong to
$MN$
or both not. A mutation of B is another bouquet with signed rotation
$(M^{-1}PN^{-1}Q)$
or
$(NPMQ)$
. Two bouquets are said to be mutant if they can be transformed into one another by a sequence of mutations.
In Definition 3.2, either
$M, N, P$
or Q can be empty. Several of
$M, N, P, Q$
can be empty at once; in particular, B is an isolated vertex if and only if
$M, N, P$
and Q are all empty at once.
Corollary 3.3. Two bouquets have the same signed intersection graph if and only if they are mutant.
Proof. Obviously, mutations preserve the intersection graphs of bouquets. Furthermore, the sign of each vertex of a signed intersection graph is not changed by a mutation. Hence if two bouquets are mutant, they have the same signed intersection graph. Conversely, if two bouquets have the same signed intersection graph, by Theorem 3.1, they are related by a sequence of mutations.
In the next section, we will show that two bouquets with the same signed intersection graph have the same partial-dual polynomial.
4 First main theorem
Now we state our first main theorem as follows.
Theorem 4.1. If two bouquets
$B_{1}$
and
$B_{2}$
have the same signed intersection graph, then
$^{\partial }\varepsilon _{B_{1}}(z)={{}^{\partial }}\varepsilon _{B_{2}}(z)$
.
Let G be a ribbon graph. Let
$e\in E(G)$
and u and v be its incident vertices, which are not necessarily distinct. The contraction [Reference Bollobás and Riordan1, Reference Ellis-Monaghan and Moffatt11]
$G/e$
of e is defined as follows. Consider the boundary component(s) of
$e \cup u\cup v$
as curves on G. For each resulting curve, attach a disc, which will form a vertex of
$G/e$
, by identifying its boundary component with the curve. Delete
$e, u$
and v from the resulting complex. Note that
$G/e=G^{e}-e$
[Reference Chmutov4], and there is a fundamental difference between graph and ribbon graph contractions. For instance, if G is the orientable ribbon graph with one vertex and one edge, then contracting that edge results in the ribbon graph comprising two isolated vertices. Ellis-Monaghan and Moffatt [Reference Ellis-Monaghan and Moffatt11] have shown that the order in which contractions are performed does not matter. Let
$A\subseteq E(G)$
. We define
$G/A$
as the result of contracting every edge of A in any order and then
$G/A=G^{A}-A.$
It is an important observation [Reference Ellis-Monaghan and Moffatt11, Reference Guo, Jin and Yan17] that the operation of the contraction does not change the number of boundary components. Let
$v(G), e(G)$
and
$f(G)$
denote the number of vertices, edges and boundary components of a ribbon graph G, respectively. To prove Theorem 4.1, we need three lemmas.
Lemma 4.2. Let B be a bouquet. Then the Euler genus
$\varepsilon (B)$
is given by the equation
$$ \begin{align*}\varepsilon(B)=1+e(B)-f(B).\end{align*} $$
Proof. Recall that if G is a connected ribbon graph, then
$2-\varepsilon (G)=v(G)-e(G)+f(G)$
. The lemma then follows from
$v(B)=1$
.
Lemma 4.3. If two bouquets
$B_{1}$
and
$B_{2}$
have the same signed intersection graph, then
$\varepsilon (B_{1})=\varepsilon (B_{2})$
.
Proof. By Corollary 3.3, we can assume that
$B_{1}$
can be transformed into
$B_{2}$
by a mutation. Let
$B_{1}=(MPNQ)$
. Then
$B_{2}=(M^{-1}PN^{-1}Q)$
or
$B_{2}=(NPMQ)$
, as in Figure 4. Denote
$B_{3}=(M^{-1}PN^{-1}Q)$
and
$B_{4}=(NPMQ)$
. By Lemma 4.2, it suffices to prove that
$f(B_{1})=f(B_{3})=f(B_{4})$
.
Figure 4 The bouquets
$B_{1}, B_{3}$
and
$B_{4}$
.
Suppose that
$G_{1}=(Me_{2}Pe_{2}Ne_{1}Qe_{1}), G_{3}=(M^{-1}e_{2}Pe_{2}N^{-1}e_{1}Qe_{1})$
and
$G_{4}=(Ne_{2}Pe_{2}Me_{1}Qe_{1})$
, as in Figure 5. Since
$$ \begin{align*}B_{i}=G_{i}-\{e_{1}, e_{2}\}=({G_{i}}^{\{e_{1}, e_{2}\}})^{\{e_{1}, e_{2}\}}-\{e_{1}, e_{2}\}={G_{i}}^{\{e_{1},e_{2}\}}/{\{e_{1},e_{2}\}}\end{align*} $$
Figure 5 The bouquets
$G_{1}, G_{3}$
and
$G_{4}$
.
for
$i\in \{1, 3, 4\}$
and contraction does not change the number of boundary components, it follows that
$f(B_{i})=f({G_{i}}^{\{e_{1},e_{2}\}})$
. For the ribbon graph
${G_{i}}^{\{e_{1},e_{2}\}}$
, arbitrarily orient the boundary of
$e_{1}$
, place an arrow on each of the two arcs where
$e_{1}$
meets vertices of
${G_{i}}^{\{e_{1},e_{2}\}}$
such that the directions of these arrows follow the orientation of the boundary of
$e_{1}$
, and label the two arrows with
$e_{1}^{\prime }$
and
$e_{1}^{\prime \prime }$
. The same operation can be drawn for
$e_{2}$
; label the two arrows with
$e_{2}^{\prime }$
and
$e_{2}^{\prime \prime }$
. Let
$v_{P}, v_{Q}$
and
$v_{MN}$
denote the vertices of
${G_{i}}^{\{e_{1},e_{2}\}}$
, which contain
$P, Q$
and
$MN$
, respectively. Let
${B_{i}}^{\prime }$
denote the ribbon graph obtained from
${G_{i}}^{\{e_{1},e_{2}\}}$
by deleting the vertices
$v_{P}, v_{Q}$
together with all the edges incident with
$v_{P}, v_{Q}$
, but keeping the marking arrows
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
, as in Figure 6. Since both labels of each edge must belong to
$MN$
or both not, this results in a bouquet with exactly two labelled arrows
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
on its boundary of the vertex, and these marking arrows only indicate the positions and no other significance. Note that if we ignore the two labelled arrows
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
, the bouquets
${B_{1}}^{\prime }$
,
${B_{3}}^{\prime }$
and
${B_{4}}^{\prime }$
are equivalent. Hence
$f({B_{1}}^{\prime })=f({B_{3}}^{\prime })=f({B_{4}}^{\prime }).$
Similarly, let
${G_{i}}^{\prime }$
denote the ribbon graph obtained from
${G_{i}}^{\{e_{1},e_{2}\}}$
by deleting the vertex
$v_{MN}$
together with all the edges incident with
$v_{MN}$
, but keeping the marking arrows
$e_{1}^{\prime }$
and
$e_{2}^{\prime }$
. This results in a ribbon graph with exactly two labelled arrows
$e_{1}^{\prime }$
and
$e_{2}^{\prime }$
on the boundaries of
$v_{P}$
and
$v_{Q}$
, as in Figure 6. Note that
${G_{1}}^{\prime }={G_{3}}^{\prime }={G_{4}}^{\prime }$
. Obviously, we can recover the boundaries of
${G_{i}}^{\{e_{1},e_{2}\}}$
from
${G_{i}}^{\prime }$
and
${B_{i}}^{\prime }$
as follows: draw a line segment from the head of
$e_{1}^{\prime }$
to the tail of
$e_{1}^{\prime \prime }$
and a line segment from the head of
$e_{1}^{\prime \prime }$
to the tail of
$e_{1}^{\prime }$
. The same operation is applied to
$e_{2}^{\prime }$
and
$e_{2}^{\prime \prime }$
. We observe that
Figure 6 The ribbon graphs
${G_{i}}^{\{e_{1},e_{2}\}}$
and
${B_{i}}^{\prime }$
for
$i\in \{1, 3, 4\}$
and
${G_{1}}^{\prime }$
.
-
(i) If
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
are contained in different boundary components of
${B_{1}}^{\prime }$
, then
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
are also contained in different boundary components of
${B_{3}}^{\prime }$
and
${B_{4}}^{\prime }$
. -
(ii) If
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
are contained in the same boundary component of
${B_{1}}^{\prime }$
, then
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
are also contained in the same boundary component of
${B_{3}}^{\prime }$
and
${B_{4}}^{\prime }$
. The arrows
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
are called consistent (inconsistent) in
${B_{1}}^{\prime }$
if these two arrows have consistent (inconsistent) orientations on the boundary component. We can also observe that if
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
are consistent (inconsistent) in
${B_{1}}^{\prime }$
, then
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
are also consistent (inconsistent) in
${B_{3}}^{\prime }$
and
${B_{4}}^{\prime }$
.
If
$e_{1}^{\prime }$
and
$e_{2}^{\prime }$
are contained in the same boundary component of
${G_{1}}^{\prime }$
and
$e_{1}^{\prime }$
,
$e_{2}^{\prime }$
are consistent in
${G_{1}}^{\prime }$
, then there are three cases, as follows.
-
Case 1. If
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
are contained in different boundary components of
${B_{1}}^{\prime }$
, then by (i), as in Figure 7.
$$ \begin{align*}f({G_{1}}^{\{e_{1},e_{2}\}})=f({G_{3}}^{\{e_{1},e_{2}\}})=f({G_{4}}^{\{e_{1},e_{2}\}})=f({G_{1}}^{\prime})+f({B_{1}}^{\prime})-2,\end{align*} $$
Figure 7 Case 1.
-
Case 2. If
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
are contained in the same boundary component of
${B_{1}}^{\prime }$
and
$e_{1}^{\prime \prime }$
,
$e_{2}^{\prime \prime }$
are consistent in
${B_{1}}^{\prime }$
, then by (ii), as in Figure 8.
$$ \begin{align*}f({G_{1}}^{\{e_{1},e_{2}\}})=f({G_{3}}^{\{e_{1},e_{2}\}})=f({G_{4}}^{\{e_{1},e_{2}\}})=f({G_{1}}^{\prime})+f({B_{1}}^{\prime})\end{align*} $$
Figure 8 Case 2.
-
Case 3. If
$e_{1}^{\prime \prime }$
and
$e_{2}^{\prime \prime }$
are contained in the same boundary component of
${B_{1}}^{\prime }$
and
$e_{1}^{\prime \prime }$
,
$e_{2}^{\prime \prime }$
are inconsistent in
${B_{1}}^{\prime }$
, then by (ii), as in Figure 9.
$$ \begin{align*}f({G_{1}}^{\{e_{1},e_{2}\}})=f({G_{3}}^{\{e_{1},e_{2}\}})=f({G_{4}}^{\{e_{1},e_{2}\}})=f({G_{1}}^{\prime})+f({B_{1}}^{\prime})-1\end{align*} $$
Figure 9 Case 3.
Similar arguments apply to the case where
$e_{1}^{\prime }$
and
$e_{2}^{\prime }$
are contained in different boundary components of
${G_{1}}^{\prime }$
or
$e_{1}^{\prime }$
and
$e_{2}^{\prime }$
are contained in the same boundary component of
${G_{1}}^{\prime }$
and
$e_{1}^{\prime }$
,
$e_{2}^{\prime }$
are inconsistent in
${G_{1}}^{\prime }$
.
Lemma 4.4 (Corollary 2.3 of [Reference Gross, Mansour and Tucker14])
Let B be a bouquet, and let
$A\subseteq E(B)$
. Then
$$ \begin{align*}\varepsilon(B^{A})=\varepsilon(A)+\varepsilon(A^{c}),\end{align*} $$
where
$A^{c}=E(B)-A$
and
$\varepsilon (A)$
is the Euler genus of the subgraph induced by A.
Proof of Theorem 4.1
For any subset
$A_{1}$
of edges of
$B_{1}$
, we also denote its corresponding vertex subset of
$SI(B_{1})$
by
$A_{1}$
. Let
$SI(B_{1})[A_{1}]$
denote the subgraph of
$SI(B_{1})$
induced by the vertex subset
$A_{1}$
. Since
$SI(B_{1})=SI(B_{2})$
, there is a corresponding subset
$A_{2}$
of vertices of
$SI(B_{2})$
such that
$SI(B_{1})[A_{1}]=SI(B_{2})[A_{2}]$
and
$SI(B_{1})[A_{1}^{c}]=SI(B_{2})[A_{2}^{c}]$
. It follows that
$\varepsilon (A_{1})=\varepsilon (A_{2})$
and
$\varepsilon (A_{1}^{c})=\varepsilon (A_{2}^{c})$
by Lemma 4.3. Hence,
$\varepsilon ({B_{1}}^{A_{1}})=\varepsilon ({B_{2}}^{A_{2}})$
by Lemma 4.4. Thus
$^{\partial }\varepsilon _{B_{1}}(z)={{}^{\partial }}\varepsilon _{B_{2}}(z)$
.
Remark 4.5. Two bouquets with different signed intersection graphs may have the same partial-dual polynomial. For example, let
$B_{1}=(1, 2, -1, 2)$
and
$B_{2}=(1, 2, -1, -2)$
. Obviously,
${{}^{\partial }}\varepsilon _{B_{1}}(z)={{}^{\partial }}\varepsilon _{B_{2}}(z)=2z+2z^{2}$
(see also [Reference Yan and Jin23]), but the signed intersection graphs of
$B_{1}$
and
$B_{2}$
are different. In fact,
$B_{2}=B_{1}^{\{1\}}$
.
5 Intersection polynomials
A signed graph
$SG$
with a
$+$
or
$-$
sign at each vertex is said to be a signed intersection graph if there exists a bouquet B such that
$SG=SI(B)$
.
Definition 5.1. The intersection polynomial
$IP_{SG}(z)$
of a signed intersection graph
$SG$
is defined by
$IP_{SG}(z):={{}^{\partial }}\varepsilon _{B}(z)$
, where B is a bouquet such that
$SG=SI(B)$
.
The well-definedness of Definition 5.1 is guaranteed by Theorem 4.1.
Theorem 5.2. Let
$SG$
be a signed intersection graph and
$v_{1}, v_{2}\in V(SG)$
. If
$v_{1}, v_{2}$
are adjacent and the vertex
$v_{1}$
is positive and of degree 1, then
$$ \begin{align*}IP_{SG}(z)=IP_{SG-v_{1}}(z)+(2z^{2})IP_{SG-v_{1}-v_{2}}(z).\end{align*} $$
Proof. Let B be a bouquet satisfying
$SG=SI(B)$
. We have
$IP_{SG}(z)={{}^{\partial }}\varepsilon _{B}(z)$
. Note that
$v_{1}, v_{2}$
correspond to two edges of B; we denote them by
$e_{1}$
and
$e_{2}$
, respectively. Since the degree of
$v_{1}$
is 1 and the sign of
$v_{1}$
is positive, it follows that
$e_{1}$
is an untwisted loop; and for any
$e\in E(B)-e_{1}-e_{2}$
, the ends of e are therefore on
$\alpha $
and
$\beta $
, or
$\gamma $
and
$\theta $
(otherwise it interlaces
$e_{1}$
), as shown in Figure 10. We partition the subsets A of
$E(B)$
into two types:
-
$\tau _{1}$
: those for which one of
$e_{1}, e_{2}$
is in A and the other is in
$A^{c}$
;
-
$\tau _{2}$
: those for which
$e_{1}, e_{2}$
are both in A or both in
$A^{c}$
.
Then
$$ \begin{align*}{{}^{\partial}}\varepsilon_{B}(z)=\sum_{A\in \tau_{1}}z^{\varepsilon(B^{A})}+\sum_{A\in \tau_{2}}z^{\varepsilon(B^{A})}.\end{align*} $$
Figure 10 Two cases for the bouquet B in the proof of Theorem 5.2.
We start by establishing a one-to-one correspondence between the set of subsets of
$E(B-e_{1})$
and
$\tau _{1}$
. Let
$D\subseteq E(B-e_{1})$
. Then
$D^{c}=E(B-e_{1})-D$
. If
$e_{2}\in D$
, take
$A=D$
so that
$A^{c}=D^{c}\cup e_{1}$
; if
$e_{2}\notin D$
, take
$A=D\cup e_{1}$
so that
$A^{c}=D^{c}$
. Furthermore, it is not difficult to see that
$\varepsilon (D)=\varepsilon (A)$
and
$\varepsilon (D^{c})=\varepsilon (A^{c})$
for each case. Then we have
$\varepsilon ((B-e_{1})^{D})=\varepsilon (B^{A})$
by Lemma 4.4. Hence,
$$ \begin{align*} \sum_{A\in \tau_{1}}z^{\varepsilon(B^{A})}={{}^{\partial}}\varepsilon_{B-e_{1}}(z). \end{align*} $$
Let
$D\subseteq E(B-e_{1}-e_{2})$
. Then
$D^{c}=E(B-e_{1}-e_{2})-D$
. Take
$A=D\cup \{e_{1},e_{2}\}$
so that
$A^{c}=D^{c}$
. Clearly,
$\varepsilon (A^{c})=\varepsilon (D^{c})$
, and it is not difficult to see that
$f(A)=f(D)$
; hence
$\varepsilon (A)=\varepsilon (D)+2$
. Then we have
$$ \begin{align*}\varepsilon(B^{A})=\varepsilon((B-e_{1}-e_{2})^{D})+2\end{align*} $$
by Lemma 4.4. Thus
$$ \begin{align*} \sum_{A\in \tau_{2}}z^{\varepsilon(B^{A})}&=2~\sum_{\{e_{1},e_{2}\}\subseteq A\in \tau_{2}}z^{\varepsilon(B^{A})}\\ &=(2z^{2})~{{}^{\partial}}\varepsilon_{B-e_{1}-e_{2}}(z). \end{align*} $$
Therefore,
$$ \begin{align*}{{}^{\partial}}\varepsilon_{B}(z)={{}^{\partial}}\varepsilon_{B-e_{1}}(z)+(2z^{2})~{{}^{\partial}}\varepsilon_{B-e_{1}-e_{2}}(z);\end{align*} $$
that is,
$$ \begin{align*}IP_{SG}(z)=IP_{SG-v_{1}}(z)+(2z^{2})IP_{SG-v_{1}-v_{2}}(z). \\[-36pt] \end{align*} $$
Example 5.3. Let
$P_{n}$
be a positive path with n vertices. Then
$IP_{P_{1}}(z)=2;$
$IP_{P_{2}}(z)=2+2z^{2};$
$IP_{P_{n+2}}(z)=IP_{P_{n+1}}(z)+2z^{2}IP_{P_{n}}(z).$
Now we give a characterisation of bouquets admitting plane partial duals in terms of intersection graphs.
Theorem 5.4. Let
$SG$
be a signed intersection graph with
$v(SG)\geq 2$
. Then
$IP_{SG}(z)$
contains a nonzero constant term if and only if
$SG$
is positive and bipartite.
Proof. Let B be a bouquet satisfying
$SG=SI(B)$
. We know that
$IP_{SG}(z)={{}^{\partial }}\varepsilon _{B}(z)$
. Since
$IP_{SG}(z)$
contains a nonzero constant term, it follows that B is a partial dual of a plane ribbon graph. According to the property that partial duality preserves orientability, we have that B is orientable, and hence
$SG$
is positive. Suppose that
$SG$
is not bipartite. Then
$SG$
contains an odd cycle C. We denote by D the edge subset of B corresponding to vertices of C. It is obvious that deleting edges cannot increase the Euler genus. Then for any subset A of
$E(B)$
, we have
$\varepsilon (A\cap D)\leqslant \varepsilon (A)$
,
$\varepsilon (A^{c}\cap D)\leqslant \varepsilon (A^{c})$
. Since
$SG$
contains an odd cycle C, there are two loops
$e_{1}, e_{2}\in A\cap D$
or
$e_{1}, e_{2}\in A^{c}\cap D$
such that their ends are met in the cyclic order
$e_{1}\cdots e_{2}\cdots e_{1}\cdots e_{2}\cdots $
when traveling around the boundary of the unique vertex of B. Then
$\varepsilon (A\cap D)+\varepsilon (A^{c}\cap D)>0$
. Thus
$\varepsilon (B^{A})=\varepsilon (A)+\varepsilon (A^{c})>0$
. But since B is a partial dual of a plane ribbon graph, there exists a subset
$A^{\prime }\subseteq E(B)$
such that
$\varepsilon (B^{A^{\prime }})=0$
, a contradiction.
Conversely, if
$SG$
is bipartite and nontrivial, then its vertex set can be partitioned into two subsets X and Y so that every edge of
$SG$
has one end in X and the other end in Y. For these two subsets X and Y of the vertex set of
$SG$
, we also denote these two corresponding edge subsets of B by X and Y. Obviously,
$X\cup Y=E(B), X\cap Y=\emptyset $
and
$\varepsilon (X)=\varepsilon (Y)=0$
. Thus
$\varepsilon (B^{X})=0$
by Lemma 4.4. Hence,
${{}^{\partial }}\varepsilon _{B}(z)$
(hence,
$IP_{SG}(z)$
) contains a nonzero constant term.
Remark 5.5. This problem has been studied in terms of separability in [Reference Moffatt19, Reference Moffatt21].
Let
$S_{n}$
be a positive star: that is, a complete bipartite graph whose vertex set can be partitioned into two subsets X and Y so that every edge has one end in X and the other end in Y with
$|X|=1$
and
$|Y|=n$
. We conclude the section by characterising partial-dual polynomials of degree 2 with nonzero constant terms using intersection polynomials and signed intersection graphs.
Theorem 5.6. Let
$SG$
be a connected signed intersection graph with
$v(SG)=v$
, and let a and b be positive integers. Then
$$ \begin{align*}IP_{SG}(z)=az^{2}+b\Longleftrightarrow SG=S_{v-1}.\end{align*} $$
Proof. For sufficiency, we have initial condition
$IP_{S_{1}}(z)=2z^{2}+2$
, and by Theorem 5.2, the recursion
$$ \begin{align*}IP_{S_{v-1}}(z)=IP_{S_{v-2}}(z)+2^{v-1}z^{2}.\end{align*} $$
Then it is easy to obtain that
$$ \begin{align*}IP_{SG}(z)=IP_{S_{v-1}}(z)=(2^{v}-2)z^{2}+2.\end{align*} $$
Conversely, since
$IP_{SG}(z)$
contains a nonzero constant term,
$SG$
is positive and bipartite by Theorem 5.4. Thus the vertex set of
$SG$
can be partitioned into two subsets X and Y so that every edge has one end in X and the other end in Y, with
$|X|=m$
and
$|Y|=n$
. If
$m=1$
or
$n=1$
, then the proof is complete. Otherwise, suppose that
$m>1$
and
$n>1$
. Since
$SG$
is connected and bipartite, there exist
$v_{1}, v_{3}\in X$
and
$v_{2}, v_{4}\in Y$
such that
$v_{1}v_{2}, v_{3}v_{4}\in E(SG)$
. Let B be a bouquet satisfying
$SG=SI(B)$
. Note that
$v_{1}, v_{2}, v_{3}$
and
$v_{4}$
correspond to four edges of B; we denote them by
$e_{1}, e_{2}, e_{3}$
and
$e_{4}$
, respectively. Thus
$e_{1}$
and
$e_{2}$
are interlaced, and so are
$e_{3}$
and
$e_{4}$
. Therefore,
$\varepsilon (\{e_{1}, e_{2}\})=2$
and
$\varepsilon (E(B)-e_{1}-e_{2})\geq \varepsilon (\{e_{3}, e_{4}\})=2$
. By Lemma 4.4, we have
$$ \begin{align*}\varepsilon(B^{\{e_{1}, e_{2}\}})=\varepsilon(\{e_{1}, e_{2}\})+\varepsilon(E(B)-e_{1}-e_{2})\geq4,\end{align*} $$
contradicting
${{}^{\partial }}\varepsilon _{B}(z)=IP_{SG}(z)=az^{2}+b$
. Hence,
$SG=S_{v-1}$
.
6 Second main theorem
Gross, Mansour and Tucker [Reference Gross, Mansour and Tucker14] discussed the simplest partial-dual polynomial: that is, a constant polynomial. They proved:
Proposition 6.1 (Propositions 3.3 and 3.6 of [Reference Gross, Mansour and Tucker14])
Let G be a connected ribbon graph. Then
${{}^{\partial }}\varepsilon _{G}(z)=2^{e(G)}$
if and only if there is a subset
$A\subseteq E(G)$
such that
$G^{A}$
is a tree.
They also considered partial-dual polynomials that are not constant polynomials and have only one term, and proved:
Proposition 6.2. (Proposition 3.7 of [Reference Gross, Mansour and Tucker14]). For any
$n>0$
and any
$m\geq n$
, there is a nonorientable ribbon graph G such that
${{}^{\partial }}\varepsilon _{G}(z)=2^{m}z^{n}$
.
For orientable ribbon graphs, Gross, Mansour and Tucker posed Conjecture 1.2, and we found an infinite family of counterexamples in [Reference Yan and Jin23]. Let t be a positive integer, and let
$B_{t}$
be a bouquet with the signed rotation
$(1, 2, 3, \cdots , t, 1, 2, 3, \cdots , t)$
.
Proposition 6.3 (Theorem 23 of [Reference Yan and Jin23])
Let t be a positive integer. Then
$$ \begin{align*} {}^{\partial}\varepsilon_{B_{t}}(z)=\left\{\begin{array}{ll} 2^{t}z^{t-1}, & \mbox{if}~t~\mbox{is odd,}\\ 2^{t-1}z^{t}+2^{t-1}z^{t-2}, & \mbox{if}~t~\mbox{is even.} \end{array} \right. \end{align*} $$
Note that
$B_{3},B_{5},B_{7},\cdots $
is an infinite family of counterexamples to Conjecture 1.2. The purpose of this section is to give a characterisation of when all partial duals of a bouquet have the same Euler genus.
6.1 Prime bouquets and our result
Moffatt [Reference Moffatt20] defined the ribbon-join operation on two disjoint ribbon graphs P and Q, denoted by
$P\vee Q$
, in two steps (see also [Reference Gross, Mansour and Tucker14]):
-
(i) Choose an arc p on the boundary of a vertex-disc
$v_{1}$
of P that lies between two consecutive ribbon ends, and choose another such arc q on the boundary of a vertex-disc
$v_{2}$
of Q. -
(ii) Paste vertex-discs
$v_{1}$
and
$v_{2}$
together by identifying the arcs p and q.
Note that, in general, the ribbon-join is not unique. A ribbon graph is called empty if it has no edges. We say that G is prime if there do not exist nonempty ribbon subgraphs
$G_{1}, \cdots , G_{k}$
of G such that
$G=G_{1}\vee \cdots \vee G_{k}$
, where
$k\geq 2$
. Clearly, we have
Lemma 6.4. A bouquet B is prime if and only if its intersection graph
$I(B)$
is connected.
Let
$B_{\overline {1}}=(1, -1)$
be the non-orientable bouquet with only one edge, and let
$\mathcal {B}=\{B_{\overline {1}}, B_{1}, B_{3}, B_{5},\cdots \}$
. Now we are in a position to state our second main theorem as follows.
Theorem 6.5. Let B be a nonempty bouquet. Then
$$ \begin{align*}{{}^{\partial}}\varepsilon_{B}(z)=2^{e(B)}z^{b}\Longleftrightarrow B=B_{t_{1}}\vee\cdots \vee B_{t_{k}},\end{align*} $$
where
$k\geq 1$
and
$B_{t_{i}}\in \mathcal {B}$
for
$1\leqslant i \leqslant k$
. Furthermore, if the number of the prime factors
$B_{\overline {1}}$
in B is
$k_{2}$
, then
$b=e(B)-k+k_{2}$
.
Note that the signed intersection graph of
$B_{\overline {1}}$
is a negative isolated vertex and the signed intersection graph of
$B_{2i+1}$
is a positive complete graph of order
$2i+1$
. In fact,
$B_{2i+1}$
is the only bouquet whose signed intersection graph is a positive complete graph of order
$2i+1$
. Restating Theorem 6.5 in the language of signed intersection graphs, we have
Corollary 6.6. Let B be a bouquet. Then
${{}^{\partial }}\varepsilon _{B}(z)=2^{e(B)}z^{b}$
if and only if each component of
$SI(B)$
is a complete graph of odd order and each vertex of
$SI(B)$
, except some isolated vertices, has positive sign.
It is easy to see that
$^{\partial }\varepsilon _{B_{1}}(z)=2$
and
$^{\partial }\varepsilon _{B_{\overline {1}}}(z)=2z$
. To prove Theorem 6.5, we shall use the following lemma.
Lemma 6.7 (Proposition 3.2 (a) of [Reference Gross, Mansour and Tucker14])
Let
$G=G_{1}\vee G_{2}$
. Then
$$ \begin{align*}^{\partial}\varepsilon_{G}(z)={{}^{\partial}}\varepsilon_{G_{1}}(z)~^{\partial}\varepsilon_{G_{2}}(z).\end{align*} $$
It suffices to show that among all prime nonorientable bouquets, there is only
$B_{\overline {1}}$
whose partial-dual polynomial has one (nonconstant) term; and among all nonempty prime orientable bouquets, there are only
$B_{1}, B_{3}, B_{5},\cdots $
whose partial-dual polynomials have one term.
Let
$G^{*}$
denote the (full) dual of a ribbon graph G. Corresponding to each edge e of G, there is an edge
$e^{*}$
of
$G^{*}$
. We view each ribbon as an oriented rectangle; then the opposing two sides lying on face-discs are called ribbon-sides [Reference Gross, Mansour and Tucker14]. We need the following lemma.
Lemma 6.8 (Table 1.1 of [Reference Gross, Mansour and Tucker14])
Let G be a ribbon graph and
$e\in E(G)$
. Then
$\varepsilon (G)=\varepsilon (G^{e})$
if and only if
$$ \begin{align*} \left\{\begin{array}{ll} e^{*}~\mbox{is proper in}~G^{*}, & \mbox{if}~e~\mbox{is an untwisted loop,}\\ e^{*}~\mbox{is an untwisted loop in}~G^{*}, & \mbox{if}~e~\mbox{is proper,}\\ e^{*}~\mbox{is a twisted loop in}~G^{*}, & \mbox{if}~e~\mbox{is a twisted loop.} \end{array} \right. \end{align*} $$
6.2 Nonorientable case
Proposition 6.9. Let B be a prime nonorientable bouquet. Then
${{}^{\partial }}\varepsilon _{B}(z)=2^{e(B)}z^{b}$
if and only if
$B=B_{\overline {1}}$
.
Proof. The sufficiency is easily verified by calculation. For necessity, since B is nonorientable, we may assume that
$e(B)\geqslant 2$
.
-
Claim 1. B does not contain a bouquet with signed rotation
$(e_{1}, e_{2}, -e_{1}, e_{2})$
.Suppose that Claim 1 is not true. Then
$e_{1}^{*}$
is a twisted loop, and
$e_{2}^{*}$
is proper in
$B^{*}$
by Lemma 6.8. Thus the two ribbon-sides of
$e_{1}$
lie on the same boundary component of B, denoted by
$C_{1}$
; and if we assign two arrows to the two ribbon-sides of
$e_{1}$
such that these two arrows are consistent on the edge boundary of
$e_{1}$
, then these two arrows are nonconsistent on
$C_{1}$
and the two ribbon-sides of
$e_{2}$
lie on different boundary components of B, as in Figure 11. Delete the edge
$e_{1}$
, and note that
$f(B)=f(B-e_{1})$
and the two ribbon-sides of
$e_{2}$
also lie on different boundary components of
$B-e_{1}$
. Hence,
$f(B-\{e_{1}, e_{2}\})=f(B-e_{1})-1$
, that is,
$f(B-\{e_{1}, e_{2}\})=f(B)-1$
. Since
$\varepsilon (e_{1}, e_{2}, -e_{1}, e_{2})=2$
and
$\varepsilon (B-\{e_{1}, e_{2}\})=e(B)-1-f(B-\{e_{1}, e_{2}\})$
by Lemma 4.2, we have by Lemma 4.4. Since
$$ \begin{align*}\varepsilon(B^{\{e_{1}, e_{2}\}})=\varepsilon(e_{1}, e_{2}, -e_{1}, e_{2})+\varepsilon(B-\{e_{1}, e_{2}\})=e(B)+1-f(B-\{e_{1}, e_{2}\})\end{align*} $$
$\varepsilon (B)=e(B)+1-f(B)$
, it is easy to check that
$\varepsilon (B)\neq \varepsilon (B^{\{e_{1}, e_{2}\}})$
, contrary to
${{}^{\partial }}\varepsilon _{B}(z)=2^{e(B)}z^{b}$
. The claim then follows.Figure 11 Proof of Proposition 6.9.
-
Claim 2. B does not contain a bouquet with signed rotation
$(e_{1}, e_{2}, -e_{1}, -e_{2})$
.Assume that Claim 2 is not true. It is easily seen that
$B^{e_{1}}$
contains a bouquet with signed rotation
$(e_{1}, e_{2}, -e_{1}, e_{2})$
. Since
${{}^{\partial }}\varepsilon _{B^{e_{1}}}(z)={{}^{\partial }}\varepsilon _{B}(z)=2^{e(B)}z^{b}$
, this contradicts Claim 1.
Since B is a nonorientable bouquet, there exists a twisted loop. Let
$e_{1}$
be any twisted loop. As B is prime and
$e(B)\geqslant 2$
, there exists a loop
$e_{2}$
such that the loops
$e_{1}$
and
$e_{2}$
alternate; this contradicts Claim 1 or 2. Hence
$e(B)=1$
: that is,
$B=B_{\overline {1}}$
.
6.3 Orientable case
Proposition 6.10. Let B be a nonempty prime orientable bouquet. Then
${{}^{\partial }}\varepsilon _{B}(z)=2^{e(B)}z^{b}$
if and only if
$B=B_{2i+1}$
for some nonnegative integer i.
Proof. The sufficiency is easily verified by Proposition 6.3. For necessity, the result is easily verified when
$e(B)\in \{1, 2\}$
. Assume that
$e(B)\geqslant 3$
. Let
$x, y, z\in E(B)$
. Note that
$x^{*}, y^{*}$
and
$z^{*}$
are proper in
$B^{*}$
by Lemma 6.8. Hence the two ribbon-sides of x (or y or z) lie on different boundary components of B. We denote the two ribbon-sides of x (or y or z) lying on the two boundary components of B by
$C_{x_{1}}$
and
$C_{x_{2}}$
(or
$C_{y_{1}}$
and
$C_{y_{2}}$
or
$C_{z_{1}}$
and
$C_{z_{2}}$
), respectively.
The following facts about ribbon graphs are well known and readily seen to be true. Deleting any edge x of an orientable ribbon graph G changes the number of boundary components by exactly one. Otherwise,
$G^{*}$
contains a twisted loop, which is contrary to the orientability of G. More specifically,
-
(T1) The two ribbon-sides of x lie on different boundary components of G if and only if
$f(G-x)=f(G)-1$
. -
(T2) The two ribbon-sides of x lie on the same boundary component of G if and only if
$f(G-x)=f(G)+1$
.
From (T1), it follows that
$f(B-x)=f(B)-1.$
Obviously,
$\varepsilon (B)=e(B)+1-f(B)$
and
$\varepsilon (B-\{x, y\})=e(B)-1-f(B-\{x, y\})$
by Lemma 4.2. There are two cases to consider:
-
Case 1. If
$B(\{x, y\})=(x, y, x, y)$
, we have by Lemma 4.4. Since
$$ \begin{align*}\varepsilon(B^{\{x, y\}})=\varepsilon(x, y, x, y)+\varepsilon(B-\{x, y\})=e(B)+1-f(B-\{x, y\})\end{align*} $$
$\varepsilon (B^{\{x, y\}})=\varepsilon (B)$
, it follows that Applying (T2) to
$$ \begin{align*}f(B-\{x, y\})=f(B)=f(B-x)+1.\end{align*} $$
$B-x$
and y, we obtain that the two ribbon-sides of y lie on the same boundary component of
$B-x$
. Hence, the two ribbon-sides of y must lie on
$C_{x_{1}}$
and
$C_{x_{2}}$
, respectively, in B. Thus
$$ \begin{align*}\{C_{x_{1}}, C_{x_{2}}\}=\{C_{y_{1}}, C_{y_{2}}\}.\end{align*} $$
-
Case 2. If
$B(\{x, y\})=(x, x, y, y)$
, then by Lemma 4.4. As
$$ \begin{align*}\varepsilon(B^{\{x, y\}})=\varepsilon(x, x, y, y)+\varepsilon(B-\{x, y\})=e(B)-1-f(B-\{x, y\})\end{align*} $$
$\varepsilon (B^{\{x, y\}})=\varepsilon (B)$
, we have Applying (T1) to
$$ \begin{align*}f(B-\{x, y\})=f(B)-2=f(B-x)-1.\end{align*} $$
$B-x$
and y, we obtain that the two ribbon-sides of y lie on different boundary components of
$B-x$
. Hence at most one of the two ribbon-sides of y lie on
$C_{x_{1}}$
and
$C_{x_{2}}$
in B. Thus
$$ \begin{align*}\{C_{x_{1}}, C_{x_{2}}\}\cap\{C_{y_{1}}, C_{y_{2}}\}\neq \{C_{x_{1}}, C_{x_{2}}\}.\end{align*} $$
-
Claim 3. B does not contain a bouquet with signed rotation
$(x, y, z, x, z, y)$
.Assume that Claim 3 is not true. Since
$B(\{x, y\})=(x, y, x, y)$
and
$B(\{x, z\})=(x, z, x, z)$
, it follows that by Case 1. Thus
$$ \begin{align*}\{C_{x_{1}}, C_{x_{2}}\}=\{C_{y_{1}}, C_{y_{2}}\}=\{C_{z_{1}}, C_{z_{2}}\}\end{align*} $$
But
$$ \begin{align*}\{C_{y_{1}}, C_{y_{2}}\}\cap\{C_{z_{1}}, C_{z_{2}}\}=\{C_{y_{1}}, C_{y_{2}}\}.\end{align*} $$
$B(\{y, z\})=(y, y, z, z)$
; this contradicts Case 2.
Suppose that
$I(B)$
is not a complete graph. Since B is prime, it follows that
$I(B)$
is connected. Then there is a vertex set
$\{v_{x}, v_{y}, v_{z}\}$
of
$I(B)$
such that the induced subgraph
$I(B)(\{v_{x}, v_{y}, v_{z}\})$
is a 2-path (see Exercise 2.2.11 [Reference Bondy and Murty2]). We may assume without loss of generality that the degree of
$v_{x}$
is 2 in
$I(B)(\{v_{x}, v_{y}, v_{z}\})$
and
$v_{x}, v_{y}, v_{z}$
are corresponding to the loops
$x, y, z$
of B, respectively. Thus
$B(\{x, y, z\})=(x, y, z, x, z, y)$
; this contradicts Claim 3. Hence,
$I(B)$
is a complete graph, and
$B=B_{2i+1}$
by Proposition 6.3.
Remark 6.11. Proposition 6.10 tells us that Conjecture 1.2 is actually true for all prime orientable bouquets except the family of counterexamples as in Proposition 6.3. We denote the two ribbon-sides of a ribbon x (or a ribbon y) lying on the two boundary components of a bouquet B by
$C_{x_{1}}$
and
$C_{x_{2}}$
(or
$C_{y_{1}}$
and
$C_{y_{2}}$
), respectively. To prove this result, both our proof and Chmutov and Vignes-Tourneret’s proof [Reference Chmutov and Vignes-Tourneret5] discuss
$\{C_{x_{1}}, C_{x_{2}}\}=\{C_{y_{1}}, C_{y_{2}}\}$
or
$\{C_{x_{1}}, C_{x_{2}}\}\neq \{C_{y_{1}}, C_{y_{2}}\}$
. Chmutov and Vignes-Tourneret’s approach is more geometric, and their proof follows directly from the construction of partial duals. Our proof is different and is based on Euler formula and Gross-Mansour-Tucker’s formula (see Lemma 4.4).
7 Concluding remarks
As shown in Remark 4.5, there are different signed intersection graphs with the same intersection polynomial. More examples could be obtained by using Theorem 6.5. For example, let
$K_{5}^{+}$
be the positive
$K_{5}$
and
$4K_{1}^{-}\cup 1K_{1}^{+}$
be the disjoint union of 4 negative isolated vertices and 1 positive isolated vertex; then
$IP_{K_{5}^{+}}(z)=IP_{4K_{1}^{-}\cup 1K_{1}^{+}}(z)=32z^{4}$
. Similar to the chromatic polynomial [Reference Dong, Koh and Teo10] and the Tutte polynomial [Reference Gong and Metsidik13], we can call two signed intersection graphs IP-equivalent if they have the same intersection polynomial. It is interesting to find more examples of equivalent signed intersection graphs and eventually clarify the IP-equivalence from the viewpoint of the structures of graphs. In particular, a signed intersection graph is IP-unique if there are no other signed intersection graphs sharing the same intersection polynomial: that is, the class of the IP-equivalence contains only one signed intersection graph. It is also interesting to find families of IP-unique signed intersection graphs.
Not every signed graph is a signed intersection graph. We define the intersection polynomial of a signed intersection graph
$SG$
to be the partial-dual polynomial of a bouquet B with
$SG=SI(B)$
. Could we redefine the intersection polynomial for signed intersection graphs independent from the bouquets? The recursion in Theorem 5.2 is an attempt, but it fails even for the negative
$v_{1}$
. If the answer is negative, can we define a polynomial on a larger set of signed graphs, including all signed intersection graphs, such that when we restrict ourselves to a signed intersection graph, it is exactly the intersection polynomial?
As a reviewer told us, Theorem 4.1 can be derived from the knowledge of matroid/delta-matroid using a few facts in [Reference Chun, Moffatt, Noble and Rueckriemen7, Reference Chun, Moffatt, Noble and Rueckriemen8]. Our proof given in this paper is completely inside the area of topological graph theory. As we mentioned in the introduction, in addition to the partial-dual (i.e., partial-
$*$
) polynomial, there are partial-
$\times $
, partial-
$*\times $
, partial-
$\times *$
and partial-
$*\times *$
polynomials [Reference Gross, Mansour and Tucker15]. For investigation of the partial-
$\bullet $
polynomial, one can focus on bouquets if
$\bullet \in \{*\times , \times *, *\times *\}$
and quasi-trees (i.e., ribbon graphs with only one face) if
$\bullet =\times $
. Could we derive something from bouquets or quasi-trees that could determine the partial-
$\bullet $
polynomial completely?
Now that nonempty bouquets whose partial-dual polynomials have only one term have been characterised completely, our Theorem 5.6 is an attempt to characterise bouquets whose partial-dual polynomials have exactly two terms. More unknowns need to be explored in this direction.
Acknowledgements
We sincerely thank the anonymous reviewers for their suggestions, which greatly improved the quality of the presentation of the paper.
Conflict of Interests
None.
Financial support
This work is supported by NSFC (Nos. 12171402, 12101600) and the Fundamental Research Funds for the Central Universities (No. 2021QN1037).
Open access
