A face polynomial invariant for embedded graphs

Introduction

Chmutov [2] introduced partial duality for embedded graphs by defining a dual operation that acts on individual edges rather than on the whole graph. This notion extends the classical geometric dual and has found considerable applications in both mathematics and physics (see, for example, [2], [7], [9] and the references therein). Later, Ellis-Monaghan and Moffatt [4] further developed the theory by considering two edge operations: taking the dual with respect to an edge and adding a half-twist to an edge. These operations generate the ribbon group action, which is isomorphic to $S_3^{|E(G)|}$ and contains geometric duality and Petrie duality as special cases. This group action supplies a powerful framework for analyzing structural features of graph polynomials, especially through the generalized transition polynomial.

Two embedded graphs are called twisted duals if they belong to the same orbit under the ribbon group action. Twisted duality provides a unified perspective for studying several topological graph polynomials. For instance, it allows the Penrose polynomial to be recovered from the transition polynomial [4], and it clarifies the relationship between the Bollobás–Riordan polynomial and the transition polynomial under appropriate restrictions [6]. These developments indicate that twisted duality has broad potential for deepening the understanding of various graph-theoretic problems.

Ellis-Monaghan and Moffatt [4] posed the following basic question:

In connection with the genus case of Problem 1.1, Gross, Mansour, and Tucker [8] introduced the partial-dual polynomial of a ribbon graph, a generating function that enumerates all partial duals according to Euler genus. This polynomial has been widely studied [3, 7, 8, 12, 13] and has also been extended to delta-matroids [14, 15, 16]. For the vertex-count case of Problem 1.1, Yan et al. [11] introduced the vertex polynomial. Their Definition 3.1 indexes the sum by orbit elements, while the paper also gives state-sum characterizations indexed by edge subsets. These conventions are not equivalent in general: distinct edge subsets may parametrize the same ribbon graph in an orbit. We therefore adopt the state-sum convention, counting each parametrizing state with multiplicity, which is the convention compatible with transition-polynomial-type generating functions.

In this paper, we introduce the face polynomial analogously, but recording face numbers under the ribbon group action. While [11] converts vertex-count variation into face-count variation via boundary-component identities, we study face-count variation directly. The face polynomial coincides with the vertex polynomial for $\langle\delta\rangle$, $\langle\delta\tau\rangle$, and $\langle\delta,\tau\rangle$. The case $\langle\tau\delta\tau\rangle$ reduces immediately, while the case $\langle\tau\rangle$ requires separate treatment. We also recast the orbit-based arguments of [11] in the state-sum framework and give full proofs, thereby addressing the face-count case of Problem 1.1 and establishing the analogous identities and recursions.

The main contributions of the paper are as follows:

1. we introduce the face polynomial for the subgroup actions generated by partial duality and partial Petrial;

2. we derive simplified state-sum formulas and deletion–contraction recursions for the face polynomial;

3. we compare the face polynomial with the vertex polynomial and the transition polynomial, and identify the subgroup actions for which the face and vertex polynomials coincide;

4. we apply the face polynomial to obtain explicit expressions, recursions, and monomial criteria for Euler-genus partial-twuality polynomials;

5. in the orientable case, we analyze the parity structure of the support of the partial-dual face polynomial and prove that both parities occur in its support whenever the graph has at least one edge; consequently, the partial-dual Euler-genus polynomial has only even exponents.

The remainder of this paper is organized as follows. In § 2, we recall the necessary background on ribbon graphs, the partial dual and partial Petrial operations, and the ribbon group action. § 3 introduces the face polynomial for various subgroups of the ribbon group, establishes simplified formulas via face-count identities, and derives recursive deletion–contraction relations. In § 4, we investigate basic properties of the face polynomial, including its evaluation at $x = 1$, invariance under the corresponding orbit, interpolation, and monomial characterizations; we also compare it with the vertex polynomial and the transition polynomial. § 5 applies the face polynomial to obtain explicit expressions and recursions for the Euler-genus partial-twuality polynomials. Finally, § 6 focuses on the orientable case, where we analyze the parity structure of the support of the partial-dual face polynomial and derive related results for the partial-dual Euler-genus polynomial.

Background on ribbon graphs and twisted duality

Ribbon graphs are the standard model for cellularly embedded graphs (see [5]) and are the main model used in this paper for graphs embedded in surfaces. We begin by recalling the standard definitions and known results needed throughout.

We first recall Chmutov’s partial dual, which dualizes an embedded graph with respect to a chosen edge subset and is one of the two generators of the ribbon group action.

The second edge operation, the partial Petrial, twists a chosen edge subset and, together with the partial dual, generates the ribbon group action.

Figure 1 illustrates how $\delta$ and $\tau$ act on a single edge. As shown in [4], the partial dual $\delta$ and the partial Petrial $\tau$ generate an action of the symmetric group $S_3$ on ribbon graphs, with presentation

Successive applications to a ribbon graph $G$ are abbreviated by

Applying $\delta$ and $\tau$ globally recovers the geometric and Petrie duals, whereas restricting them to an edge subset yields their partial counterparts. Iterating these operations produces further classes of ribbon graphs, which are summarized in Table 1 and formalized in Definition 2.4.

Operation(s)	Order	Action on $E(G)$	Action on a subset of $E(G)$
$\delta$	2	geometric dual	partial dual
$\tau$	2	Petrie dual	partial Petrial
$\tau\delta\tau$	2	Wilson dual	partial Wilsonial
$\delta\tau$ or $\tau\delta$	3	triality	partial triality
$\delta$ and $\tau$	6	a direct derivative	twisted dual

The notation $\bigsqcup_{i=1}^{n} A_i = E(G)$ means that $A_1,\ldots,A_n$ are pairwise disjoint and their union is $E(G)$; some of the $A_i$ may be empty.

The following basic properties of twisted duality will be used repeatedly; in particular, they allow us to reduce many computations to single edges and to connected components.

The face polynomial of ribbon graphs

To capture the effect of the ribbon group action on face counts, we introduce the following generating function. Here $f(G)$ denotes the number of boundary components of a ribbon graph $G$.

Two immediate reductions follow from the definition and simplify the subsequent discussion.

To translate face numbers under the group action into those of spanning subgraphs, we need the following identities. Here $G-A$ denotes the ribbon subgraph obtained by deleting the edges in $A$ while retaining all vertices.

Proof. By Proposition 2.5(2), it remains only to verify the case $A=\{e\}$, which is readily verified from Figure 2. $\square$

The next lemma provides a useful normal form for twisted duals and will be used to rewrite the state sums below. Recall that, for $A\subseteq E(G)$, $G/A$ denotes the ribbon graph obtained by contracting all edges in $A$ in the sense of [5], and $G/e:=G/\{e\}$ for $e\in E(G)$.

Combining the reductions in Remark 3.2 with Lemmas 3.3 and 3.4, we obtain the following face-count expressions for the face polynomial.

As a consequence of Theorem 3.5, the face polynomial for the full ribbon group action can be reduced to that for the $\langle\delta\tau\rangle$-action.

Consequently, we only need to investigate the face polynomial for $\pi\in\{\langle\delta\rangle,\langle\tau\rangle,\langle\delta\tau\rangle\}$.

We now show that the face polynomial obeys deletion–contraction type recursions, reflecting the edge operations that generate the ribbon group action.

Proof. Partitioning edge subsets by $e$:

where $\pi\in\{\delta,\tau\}$.

(1) By Lemma 3.3, for $A', A \subseteq E(G)\setminus\{e\}$:

and, by Lemma 3.4, we have

Hence,

(2)

and, by Lemma 3.4, we have

Hence,

(3) By Theorem 3.5, we decompose the sum based on the position of edge $e$:

Case 1: $e \in A_3$.

Case 2: $e \in A_1$.

Case 3: $e \in A_2$.

Basic properties of the face polynomial

For a ribbon graph $G$, let $v(G)$ and $e(G)$ denote its numbers of vertices and edges, respectively. For a polynomial $f(x)=\sum_{i=0}^{m}a_i x^i$, its support is defined by $\operatorname{Supp}(f)=\{i:a_i\ne0\}$, the set of indices of the non-zero coefficients. We call a polynomial with nonnegative coefficients interpolating if its support contains every integer between its minimum and maximum degrees.

We begin with basic evaluations and structural properties that follow directly from the state-sum definition and orbit invariance.

Proof. (1) Evaluating $FP_{\langle\delta\rangle}(G,1)$ and $FP_{\langle\tau\rangle}(G,1)$ yields the total number of edge subsets of the graph $G$, namely $2^{e(G)}$. On the other hand, $FP_{\langle\delta\tau\rangle}(G,1)$ enumerates all partial trialities of $G$ and equals $3^{e(G)}$, since each edge admits exactly three choices: the identity, $\delta\tau$, and $\tau\delta$.

(2) Let $H\in\operatorname{Orb}_{\langle\delta\rangle}(G)$. Then $H=G^{\delta(A)}$ for some $A\subseteq E(G)$. Thus

for all $B\subseteq E(G)$. Clearly, the map $B\mapsto A\mathbin{\triangle}B$ is a bijection, so $FP_{\langle\delta\rangle}(G,x)=FP_{\langle\delta\rangle}(H,x)$. Analogously, $FP_{\langle\tau\rangle}(G,x)=FP_{\langle\tau\rangle}(H,x)$. Now let $H \in\operatorname{Orb}_{\langle\delta\tau\rangle}(G)$. Then $H = G^{\tau\delta}(A_1)\delta\tau(A_2)$ for two disjoint edge subsets $A_1,A_2 \subseteq E(G)$. For any pair of disjoint edge subsets $B_1,B_2 \subseteq E(G)$, we have

The mappings $B_1 \mapsto((A_2\setminus B_2)\mathbin{\triangle}B_1)\cup(A_1\cap B_2)$ and $B_2 \mapsto(A_1\mathbin{\triangle}(B_2\setminus A_2))\cup(A_2\cap B_1)$ are both bijections. Consequently, $FP_{\langle\delta\tau\rangle}(G,x)=FP_{\langle\delta\tau\rangle}(H,x)$.

Therefore, for each $\bullet\in\{\langle\delta\rangle,\langle\tau\rangle,\langle\delta\tau\rangle\}$, the face polynomial $FP_{\bullet}(G,x)$ depends only on the orbit of $G$. It therefore takes the same value for every graph $H$ in $\operatorname{Orb}_{\bullet}(G)$.

(3) Let $H\in\operatorname{Orb}_{\bullet}(G)$ satisfy that the maximum degree of $FP_{\bullet}(G,x)$ is equal to $f(H)$. The case $f(H)=1$ is trivial, so we assume $f(H)\ge2$. There then exists an edge $e$ that is incident to two distinct faces. Applying one of the operators $\delta(e)$, $\tau(e)$, $\delta\tau(e)$ merges these two faces into one, which decreases the total number of faces by 1. As a result, $FP_{\bullet}(H,x)$ is an interpolating polynomial of minimum degree 1. ∎

The preceding formulas allow us to compare the face polynomial with the vertex polynomial. By Theorems 3.5 and 4.2, we have

This theorem shows that, for the subgroup actions considered here, the face and vertex polynomials share the same state-sum structure. Consequently, several properties of the vertex polynomial derived in [11] carry over directly to the face polynomial.

(3) $FP_{\langle\delta\tau\rangle}(G,x)$ is never a monomial.

Proof. Items (1) and (3) are immediate consequences of Theorem 4.3 and Proposition 4.4 from [11]. We now proceed to prove assertion (2).

For sufficiency, let $G$ be a tree with $m$ edges. Then $G=G^{\tau(A)}$ for any $A\subseteq E(G)$. A direct computation gives

which explicitly shows that the polynomial is a monomial.

For necessity, assume that $FP_{\langle\tau\rangle}(G,x)$ is a monomial. Proposition 4.1(1) and (3) then give $FP_{\langle\tau\rangle}(G,x)=2^{m}x$. Suppose, for contradiction, that $G$ is not a tree. Then $G$ contains a cycle. By contracting all edges of a spanning tree of $G$, we obtain a bouquet $B$. Clearly, $B\not\cong K_1$. If $B$ has a trivial loop (i.e., a loop not interlaced with any other loop), then $FP_{\langle\tau\rangle}(B,x)$ is not a monomial. If $B$ has exactly two interlaced loops that are not interlaced with any other loop, then $FP_{\langle\tau\rangle}(B,x)$ is again not a monomial. If $B$ has more than two interlaced loops, we can choose two of these loops that lie at the ends of the interlaced family (the “end loops”) and contract all the other loops. This yields a bouquet $B'$ consisting only of the two chosen end loops; in each case—whether the two loops form a trivial 2-cycle, two interlaced loops, or two trivial loops—$FP_{\langle\tau\rangle}(B',x)$ is not a monomial. By Theorem 3.7(2), the deletion–contraction recursion reduces the computation to $B$ or $B'$. Since all coefficients are nonnegative, no cancellation can occur. This implies that $FP_{\langle\tau\rangle}(G,x)$ is not a monomial, a contradiction. Therefore, $G$ must be a tree.

Remark 4.5. It is shown in [11] that the vertex polynomial agrees with the topological transition polynomial $Q(G;(\alpha,\beta,\gamma),x)$ introduced in [4] under certain specializations. By Theorem 3.7, the face polynomial admits a similar identification with the same transition polynomial when the indeterminates $\alpha,\beta,\gamma$ are restricted to values in $\{0,1\}$. Moreover, Theorem 4.3 shows that the face and vertex polynomials coincide for the subgroup actions $\langle\delta\rangle$, $\langle\delta\tau\rangle$, and $\langle\delta,\tau\rangle$. These observations place the face polynomial within the broader framework of transition polynomials and clarify its relation to the vertex polynomial. The main contribution of this paper is a direct face-count formulation and a set of tools that streamline the study of Euler-genus partial-twuality polynomials; the parity results in § 6 illustrate this utility. These connections also highlight the interplay among the face polynomial, the vertex polynomial, and the transition polynomial, and provide complementary perspectives on our results.

We now apply the face polynomial to the Euler-genus partial-twuality polynomials.

Applications to Euler-genus partial-twuality polynomials

The Euler genus of a ribbon graph $G$ is defined as

where $c(G)$ is the number of connected components. It equals twice the genus if the embedding is orientable, and equals the crosscap number if the embedding is non-orientable. Recall that Gross, Mansour, and Tucker [8] introduced the partial-dual polynomial of a ribbon graph as a generating function that enumerates all partial duals of the ribbon graph according to Euler genus. Since the effect of individual group elements has been examined, it is natural to study the action of the whole subgroup on the Euler genus.

Using Euler’s formula (2), we can express the Euler-genus partial-twuality polynomials in terms of face and vertex counts.

Substituting the face and vertex-count identities from Theorems 3.5 and 4.2 gives the following explicit formulas.

The recursions for the face polynomial transfer directly to the Euler-genus partial-twuality polynomials. Using Theorems 3.7, 4.2, 4.3, and Proposition 5.3, we obtain the following recursions.

Using Theorems 4.2 and 4.3 together with Proposition 4.4, we translate the monomial characterizations of the face polynomial into the following monomial criteria for Euler-genus partial-twuality polynomials.

Supports in the orientable case

A ribbon graph is orientable if its underlying surface is orientable, and non-orientable otherwise.

The face polynomial $FP_{\langle\delta\rangle}(G,x)$ is known to be interpolating. However, the arithmetic structure of its support remains unexplored. For orientable ribbon graphs, Euler’s formula imposes a parity constraint on the face count of any subgraph whose number of edges has a prescribed parity.

We first record a parity constraint for orientable ribbon graphs; it is the key tool for the support analysis in this section.

This parity lemma has the following immediate consequence.

Since, for $n\geq1$, there is a one-to-one correspondence between the even-sized subsets and the odd-sized subsets of an $n$-element set, Lemma 6.1 implies the following proposition.

Recall that the face polynomial is defined for several subgroup actions: $\langle\delta\rangle$, $\langle\tau\rangle$, and $\langle\delta\tau\rangle$. Their supports are naturally related.

Declaration of competing interest

The authors declare no competing interests.

Acknowledgements

This work is supported by National Natural Science Foundation of China (Grant Number: 12661073) and Natural Science Foundation of Xinjiang (Grant Number: 2024D01A89).

Data availability

No data was used for the research described in the article.