Relations between global forcing number and maximum anti-forcing number of a graph¹¹1This work is supported by NSFC (Grant No. 11871256)

In this paper, we only consider finite simple graphs with at least one perfect matching. Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. We denote the order of $G$ by $v(G)=|V(G)|$, and the size by $e(G)=|E(G)|$. An edge subset $M$ of $G$ is a perfect matching (1-factor or a Kekulé structure in chemical literature), if every vertex of $G$ is incident with exactly one edge in $M$.

In 1987, Klein and Randić [15] introduced the innate degree of freedom of a Kekulé structure, which plays an important role in the resonance theory in chemistry. Harary et al. [13] called it as forcing number: If a subset $S$ of a perfect matching $M$ in a graph $G$ is contained in exactly one perfect matching of $G$, then $S$ is a forcing set of $M$. The minimum cardinality over all forcing sets of $M$ is called the forcing number of $M$, denoted by $f(G,M)$. The minimum (resp. maximum) forcing number of $G$ is denoted by $f(G)$ (resp. $F(G)$). For a hypercube $Q_{n}$, Diwan [9] showed that $f(Q_{n})=2^{n-2}$, confirming a conjecture by Pachter and Kim [24]. For a hexagonal system, Xu et al. [32] and Zhou and Zhang [35] showed that the maximum forcing number is equal to its Clar number (resonant number). For polyomino graphs and (4,6)-fullerenes (also called Birkoff-Von Neumann graphs) the same result also holds (cf. [34, 36, 27]).

As early as 1997, Li [19] raised the concept of forcing single edge (i.e. anti-forcing edge). In 2007, Vukičević and Trinajstić [30, 31] introduced the anti-forcing number of a graph $G$. In general, recently Lei et al. [18] and Klein and Rosenfeld [16] independently defined the anti-forcing number of a single perfect matching $M$ of a graph $G$. A subset of $E(G)\setminus M$ is an anti-forcing set of $M$ if its removal results in a graph with a unique perfect matching. The minimum cardinality of an anti-forcing set of $M$ is called the anti-forcing number of $M$ in $G$, denoted by $af(G,M)$. The minimum (resp. maximum) anti-forcing number of $G$ is denoted by $af(G)$ (resp. $Af(G)$). Lei et al. [18] and Shi et al. [27] respectively showed that the maximum anti-forcing number of hexagonal systems and (4,6)-fullerenes are equal to their Fries numbers. For upper bounds on maximum anti-forcing number of graphs, see [7, 28]

The concept of “global forcing” was introduced by Vukičević [29] to distinguish all perfect matchings of a graph. An edge subset $S$ of $G$ is called a global forcing set of $G$, if no two distinct perfect matchings of $G$ coincide on $S$. The minimum cardinality of a global forcing set of $G$ is the global forcing number of $G$, denoted by $gf(G)$. Since then, some scholars studied the global forcing numbers of some chemical graphs, see [10, 1, 20, 33, 26, 29].

In this paper, we readily find that $gf(G)\geq F(G)$ for any graph $G$. A relation $Af(G)\geq F(G)$ has been already revealed [18]. Došlić [10] and Deng and Zhang [8] respectively proved that the global forcing number and the maximum forcing number of a graph have the cyclomatic number as a common upper bound. Motivated by the above facts, it is natural to consider relations between the global forcing number and the maximum anti-forcing number of a graph.

For (4,6)-fullerene graph $G$, a plane cubic graph whose faces are hexagons and squares, Cai and Zhang [1] gave a sharp lower bound on global forcing number: $gf(G)\geq\lceil\frac{2f}{3}\rceil$, and Shi and Zhang [27] obtained a formula for the maximum anti-forcing number: $Af(G)=\left\lfloor\frac{v}{3}\right\rfloor+2$, where $f$ and $v$ are the numbers of faces and vertices of $G$ respectively. By Euler’s formula we have $2f=v+4$, which implies that $\lceil\frac{2f}{3}\rceil=\left\lfloor\frac{v}{3}\right\rfloor+2$. Accordingly we have that $gf(G)\geq Af(G)$ for any (4,6)-fullerene graph $G$.

For a general bipartite graph $G$ with $2n$ vertices, luckily we can prove that $gf(G)\geq Af(G)$ by finding a special edge $e$ of $G$ with $gf(G)\geq gf(G-e)+1$ and $Af(G-e)+1\geq Af(G)$. Moreover, we get that $gf(G)-Af(G)\leq\frac{1}{2}(n-1)(n-2)$, and equality holds if and only if $G$ is isomorphic to $K_{n,n}$.

The next question is whether we can extend the above relation $gf(G)\geq Af(G)$ to non-bipartite graphs. In this paper we give a negative answer by constructing a matching covered graph $G_{k}$ for any positive integer $k$ such that $gf(G_{k})-Af(G_{k})=-k$. However we can extend such a relation to conformal graphs which has a close connection with classical problems as perfect matching polytope and tight cut decomposition in matching theory of graphs [22, 12, 11, 21].

Let $\mathcal{G}$ denote the set of graphs $G$ with a perfect matching such that $G$ contains no two disjoint odd cycles $C$ and $C^{\prime}$ such that $G-C-C^{\prime}$ has a perfect matching. We reveal a novel substructure of a graph with a unique perfect matching $M$ and the minimum degree larger than $1$, which consists of two disjoint odd cycles and an odd path connecting them such that $M$ contains a perfect matching of it. Based on this substructure, we show that $gf(G)\geq Af(G)$ for a graph $G\in\mathcal{G}$ by finding a $1$-degree vertex from a special subgraph of $G$ with a unique perfect matching. As a corollary, we have that for a graph $G$ whose perfect matching polytope consists of non-negative $1$-regular vectors, $G\in\mathcal{G}$ and thus $gf(G)\geq Af(G)$.

In particular, for a brick $G$ (3-connected bicritical graph), de Carvalho, Lucchesi and Murty [4] showed that $G\in\mathcal{G}$ if and only if the perfect matching polytope of $G$ consists of non-negative $1$-regular vectors, and if and only if $G$ is solid (without non-trivial separating cuts). For a general graph, the above three conditions are not necessarily equivalent. For more details on solid bricks, see [2, 23, 12, 3, 6, 5]. In 2013, Kawarabayashi [14] gave a simpler proof for the characterization of the graphs without two disjoint odd cycles.

Finally, for a connected graph $G$, we get tight upper and lower bounds on $gf(G)-Af(G)$: $-\frac{1}{2}(n^{2}-n-2)\leq gf(G)-Af(G)\leq(n-1)(n-2)$, where the second equality holds if $G$ is isomorphic to complete graph $K_{2n}$.

For a vertex $v$ in $G$, we denote the set of all neighbors of $v$ by $N_{G}(v)$. And the cardinality of $N_{G}(v)$ is said to be the degree of $v$, denoted by $d_{G}{(v)}$. Let $\Delta(G)$ and $\delta(G)$ denote the maximum and minimum degree of $G$ respectively. Lei et al. [18] showed the following relations between the forcing number and the anti-forcing number of a perfect matching of a graph.

The cyclomatic number of a connected graph $G$ is $c(G)=e(G)-v(G)+1$. In 2017, Deng and Zhang [8] proved that the maximum forcing number of $G$ is less than or equal to $c(G)$.

For two sets $A$ and $B$, the symmetric difference of $A$ and $B$ is defined by $A\oplus B=A\cup B-A\cap B$. Let $G$ be a graph with at least one perfect matching $M$. We say a subgraph $H$ of $G$ is nice if $G-V(H)$ has a perfect matching. For convenience, we denote $G-V(H)$ by $G-H$. An even cycle $C$ of $G$ is called an M-alternating cycle, if the edges of $C$ appear alternately in $M$ or not. An even cycle $C$ is a nice cycle of $G$ if and only if $G$ has two perfect matchings $M_{1}$ and $M_{2}$ such that $M_{1}\oplus M_{2}=E(C)$. In 2007, Došlić [10] gave the following result.

We denote the set of all perfect matchings of a graph $G$ by $\mathcal{M}$, and $\Phi(G)=|\mathcal{M}|$. Došlić gave the following lower bound on the global forcing number.

The following results give equivalent conditions for forcing sets, anti-forcing sets and global forcing sets of a graph.

From these equivalent definitions, we can find some correlations.

Let $H$ be a subgraph of $G$. For any $F\subseteq E(G)$, we denote $F\cap E(H)$ by $F|_{H}$.

The lemma gives a characterization for the complement of a minimum global forcing set $S$ of $G$. The following result shows that the addition of some edges in $G$ to $G-S$ results in a graph with a unique perfect matching.

If $G$ has a 1-degree vertex $u$, then $u$ is called a pendant vertex and $uv$ a pendant edge, where $v$ is the neighbor of $u$. The deletion of $u$ and $v$ with their incident edges is called a leaf matching operation (simply $LM$ operation). Next, we can see that $LM$ operation has no effect on the minimum global forcing sets of a graph.

We consider some relations between the global forcing number and the maximum anti-forcing number of graphs by starting bipartite graphs in this section. The following structure of a bipartite graph with a unique perfect matching will play an important role.

Combining Theorem 3.1 and Lemma 2.12, we can obtain the following critical result that connects a minimum global forcing set of a bipartite graph $G$ with anti-forcing sets of a perfect matching of $G$.

From the lemma, we can obtain a main result in comparing the global forcing number and the maximum anti-forcing number of a bipartite graph.

Next we will fix the order of a graph, but ignore its size to estimate the difference between the global forcing number and the maximum anti-forcing number of bipartite graphs.

Shi et al. [28] gave an upper bound of the maximum anti-forcing number of graphs.

A perfect matching $M$ of $G$ is said to be nice, if $M$ satisfies all equalities in Theorem 3.6. A characterization for a nice perfect matching of a graph was given as follows [28].

In the following, we will give a graph $G$ such that $gf(G)-Af(G)$ is one less than the upper bound in Theorem 3.5, i.e. $gf(G)-Af(G)=\frac{1}{2}(n^{2}-3n)$. A cycle $C$ in a graph $G$ is a Hamilton cycle if $V(C)=V(G)$.

A connected graph $G$ is called matching covered, if every edge of $G$ belongs to a perfect matching of $G$. For a graph $G$, $\mathbb{R}^{E(G)}$ denotes the set of all vectors whose entries are indexed by the edges of $G$. For any perfect matching $M$ of $G$, the incidence vector of $M$ is denoted by $q^{M}$. The perfect matching polytope of $G$ is the convex hull of $\left\{q^{M}:M\in\mathcal{M}\right\}$, denoted by $PM(G)$. In a landmark paper, Edmonds [11] gave a linear inequality description of $PM(G)$. For any $\bm{x}\in\mathbb{R}^{E(G)}$ and $F\subseteq E(G)$, let $\bm{x}(F)=\sum\limits_{e\in F}\bm{x}(e)$. For a nonempty subset $U\subset V(G)$, $\partial_{G}(U)$ represents for a cut, the set of edges which have exactly one end vertex in $U$. If $U$ is a singleton, then $\partial_{G}(U)$ is a trivial cut.

A vector $\bm{x}$ in $\mathbb{R}^{E(G)}$ is 1-regular if $\bm{x}(\partial_{G}(v))=1$, for all $v\in V(G)$. For a cut $C:=\partial_{G}{(X)}$ of $G$, we denote the graph obtained from $G$ by shrinking the shore $\overline{X}=V(G)-X$ to a vertex by $G\left\{X\right\}$. We refer to $G\left\{X\right\}$ and $G\left\{\overline{X}\right\}$ as the $C$-contractions of $G$. A cut $C$ of a matching covered graph $G$ is a separating cut if both of the $C$-contractions of $G$ are also matching covered, and is tight if $|C\cap M|=1$ for all $M\in\mathcal{M}$. Every tight cut is separating, but the converse is not true. A matching covered graph is solid if all separating cuts of it are tight. A brick is a non-bipartite matching covered graph satisfying that all tight cuts of it are trivial.

de Carvalho et al. [4] pointed out that in 2003 Reed and Wakabayashi had already showed that (i) and (ii) are equivalent in Theorem 4.2, and gave a new proof to it and proved the equivalence of (i) and (iii).

In 1959, Kotzig [17] showed the following property of the graphs with a unique perfect matching.

For the graphs $G$ with a unique perfect matching, we come to a deeper structure property: $G$ contains either a pendant vertex as Theorem 3.1 in the bipartite case or an odd dumbbell (see Fig. 3): two disjoint odd cycles connected by one path of odd length.

Now we can extend the relation $gf(G)\geq Af(G)$ to the class of graphs $\cal G$. First we extend Lemma 3.2 as follows.