Graphs with large maximum forcing number
Qianqian Liu, Ajit A. Diwan, Heping Zhang · 2025
Read Graphs with large maximum forcing number by Qianqian Liu, Ajit A. Diwan, Heping Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-22761.txt.
Introduction
Qianqian Liu, Ajit Diwan, and Heping Zhang work in pure graph theory on the forcing number of perfect matchings. A forcing set is a small part of a perfect matching whose presence pins down the whole matching uniquely. A graph's maximum forcing number is the largest such minimum over all its perfect matchings. A conjecture linked the number of edges in a graph to this maximum, predicting a lower bound on edges.
The authors confirm that conjecture and turn it into an upper bound on the maximum forcing number in terms of the edge count. For extreme graphs, and bipartite graphs close to that value, they show any two perfect matchings can be transformed into each other by switches along short even cycles. They also settle the possible minimum forcing numbers for the near-extreme bipartite case and answer a follow-up question for small values.
Catalog record
| CREATOR | Qianqian Liu, Ajit A. Diwan, Heping Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-22761
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graphs with large maximum forcing number Qianqian Liu, Ajit A. Diwan, Heping Zhang Abstract Abstract : For a graph G with order 2n and a perfect matching, let f(G) and F(G) denote the minimum and maximum forcing number of G respectively. Then 0\leq f(G)\leq F(G)\leq n-1 . Liu and Zhang [ 10 ] ever proposed a conjecture: e(G)\geq\frac{n^{2}}{n-F(G)} , where e(G) denotes the number of edges of G . In this paper we confirm this conjecture and obtain F(G)\leq n-\frac{n^{2}}{e(G)} . If F(G)=n-1 , Liu and Zhang [ 9 ] proved that any two perfect matchings of G can be obtained from each other by a series of matching switches along 4-cycles. If G is bipartite and F(G)\geq n-k , 1\leq k\leq n-1 , we show that any two perfect matchings of G can be obtained from each other by a series of matching switches along even cycles of length at most 2(k+1) . Finally, we ask whether f(G)\geq\lceil\frac{n}{k}\rceil-1 holds for such bipartite graphs G , and give positive answers for the cases k=1,2 . Further we show all minimum forcing numbers of the bipartite graphs G of order 2n and with F(G)=n-2 form an integer interval [\lfloor\frac{n}{2}\rfloor,n-2] . Keywords : Perfect matching; Maximum forcing number; Bipartite graph; Matching switch AMS Subject Classification: 05C70, 05C35 1 Introduction We consider only finite and simple graphs. Let G be a graph with vertex set V(G) and edge set E(G) . The order of G is the number of vertices in G . A matching M in G is an edge subset such that no two edges of M have an endvertex in common. The vertices incident to the edges of M are called M - saturated , and the others are called M - unsaturated . A perfect matching of G is a matching that saturates every vertex. Let G be a graph with a perfect matching M . A subset of M is called a forcing set of M in G if it is not contained in any other perfect matching of G . The smallest cardinality of a forcing set of M is called the forcing number of M , denoted by f(G,M) . The concept of forcing number was originally introduced by Klein and Randić [ 7 ] under the name of the innate degree of freedom, which plays an important role in resonance theory. The minimum and maximum forcing numbers of G is the minimum and maximum values of forcing numbers over all perfect matchings of G , denoted by f(G) and F(G) , respectively. Afshani et al. [ 2 ] showed that computing the minimum forcing number is NP-complete for bipartite graphs with the maximum degree 4. However the complexity of computing the maximum forcing number of a graph is unknown. For forcing numbers of perfect matchings of graphs and some related topics, readers may refer to two surveys [ 3 , 13 ] . Let G be a graph of order 2n and with a perfect matching. Then 0\leq f(G)\leq F(G)\leq n-1 . Liu and Zhang [ 10 ] obtained a lower bound of e(G) by using maximum forcing number F(G) , where e(G) denotes the number of edges of G . To improve the bound they proposed the following conjecture. Conjecture 1.1 . [ 10 ] Let G be a graph with order 2n and a perfect matching. Then e(G)\geq\frac{n^{2}}{n-F(G)},\text{ equivalently, }F(G)\leq n-\frac{n^{2}}{e(G)}. For some special cases F(G)\leq\frac{n}{2} and F(G)=1,2 , the conjecture was already confirmed. In this paper we completely confirm this conjecture. Applying this bound on the d -dimensional hypercube Q_{d} , we obtain that F(Q_{d})\leq(1-\frac{1}{d})2^{d-1} ; see Section 3. Che and Chen [ 3 ] proposed a problem: How to characterize the graphs G with f(G)=n-1 . For bipartite graphs, they [ 4 ] obtained that f(G)=n-1 if and only if G is complete bipartite graph K_{n,n} . Moreover, Liu and Zhang [ 9 ] solved the problem by obtaining the following result. Theorem 1.2 . [ 9 ] Let G be a graph of order 2n . Then f(G)=n-1 if and only if G is a complete multipartite graph with each partite set having size no more than n or a graph obtained by adding arbitrary additional edges in one partite set to complete bipartite graph K_{n,n} . However, it is difficult to characterize the graphs G with order 2n and F(G)=n-1 , a larger class of graphs. Some interesting properties have been already revealed. Theorem 1.3 . [ 9 ] If G is a graph of order 2n and with F(G)=n-1 , then the forcing spectrum (the set of forcing numbers of all perfect matchings) is continuous. Theorem 1.4 . [ 9 ] All minimum forcing numbers of the graphs G with order 2n and F(G)=n-1 form an integer interval [\lfloor\frac{n}{2}\rfloor,n-1] . To prove Theorem 1.3 they showed that any two perfect matchings of G can be obtained from each other by applying a series of matching switches along 4-cycles. In Sections 4 and 5 of this paper, we consider all bipartite graphs G of order 2n and with F(G)\geq n-k for 1\leq k\leq n . In section 4 we prove that any two perfect matchings of G can be obtained from each other by applying a series of matching switches along even cycles of length at most 2(k+1) . In Section 5, we propose a problem: does f(G)\geq\lceil\frac{n}{k}\rceil-1 always hold? We give positive answers for the cases k=1,2 . Further we show all minimum forcing numbers of the bipartite graphs G of order 2n and with F(G)=n-2 form an integer interval [\lfloor\frac{n}{2}\rfloor,n-2] . 2 Preliminary In this section, we give some notations and prove an important lemma. For sets A and B , the symmetric difference of A and B is defined as A\oplus B:=(A\setminus B)\cup(B\setminus A) . For a perfect matching M of a graph G , a path or cycle is M -alternating if its edges appear alternately in M and off M . If C is an M -alternating cycle of length 2l for l\geq 2 , then the symmetric difference M\oplus E(C) , is called a matching switch on M along C of length 2l (simply matching l -switch ), to get another perfect matching of G . The degree of a vertex v in G , denoted by d_{G}(v) , is the number of edges incident to v . The minimum and maximum degree of G are denoted by \delta(G) and \Delta(G) , respectively. The neighborhood of v , denoted by N_{G}(v) , is the set of vertices adjacent to v . We denote a cycle with l(\geq 3) vertices by C_{l} . A graph G is called C_{l} -free if G contains no induced subgraphs isomorphic to C_{l} . A chord of a cycle C is an edge not in C whose endvertices lie in C . For a vertex subset S of G , G[S] denotes the subgraph of G induced by S whose vertex set is S and edge set consisting of all edges of G with both endvertices in S . In a word, G[S] is the subgraph G-V(G)\setminus S , obtained from G by deleting all vertices in V(G)\setminus