Relations between global forcing number and maximum anti-forcing number of a graph

DOI10.1016/J.DAM.2022.01.010MaRDI QIDQ2078844zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 4 March 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.05746

zbMATH Keywords

Birkhoff-von Neumann graphglobal forcing numbermaximum anti-forcing numberperfect matchingperfect matching polytopesolid brick

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The global forcing number of a graph G is the minimal cardinality of an edge subset discriminating all perfect matchings of G, denoted by gf(G). For any perfect matching M of G, the minimal cardinality of an edge subset S in E(G)-M such that G-S has a unique perfect matching is called the anti-forcing number of M,denoted by af(G, M). The maximum anti-forcing number of G among all perfect matchings is denoted by Af(G). It is known that the maximum anti-forcing number of a hexagonal system equals the famous Fries number. We are interested in some comparisons between the global forcing number and the maximum anti-forcing number of a graph. For a bipartite graph G, we show that gf(G)is larger than or equal to Af(G). Next we mainly extend such result to non-bipartite graphs, which is the set of all graphs with a perfect matching which contain no two disjoint odd cycles such that their deletion results in a subgraph with a perfect matching. For any such graph G, we also have gf(G) is larger than or equal to Af(G) by revealing further property of non-bipartite graphs with a unique perfect matching. As a consequence, this relation also holds for the graphs whose perfect matching polytopes consist of non-negative 1-regular vectors. In particular, for a brick G, de Carvalho, Lucchesi and Murty [4] showed that G satisfying the above condition if and only if G is solid, and if and only if its perfect matching polytope consists of non-negative 1-regular vectors. Finally, we obtain tight upper and lower bounds on gf(G)-Af(G). For a connected bipartite graph G with 2n vertices, we have that 0 leq gf(G)-Af(G) leq 1/2 (n-1)(n-2); For non-bipartite case, -1/2 (n^2-n-2) leq gf(G)-Af(G) leq (n-1)(n-2).

Recommendations

• Anti-forcing numbers of perfect matchings of graphs
• Some tight bounds on the minimum and maximum forcing numbers of graphs
• Extremal anti-forcing numbers of perfect matchings of graphs
• Forcing and anti-forcing edges in bipartite graphs
• Global forcing number of benzenoid graphs

Cites work

• A generalization of Little's theorem on Pfaffian orientations
• A maximum resonant set of polyomino graphs
• A minimax result for perfect matchings of a polyomino graph
• A simpler proof for the two disjoint odd cycles theorem
• Anti-forcing numbers of perfect matchings of graphs
• Anti-forcing spectra of perfect matchings of graphs
• Birkhoff-von Neumann graphs that are PM-compact
• Brick decompositions and the matching rank of graphs
• Clar sets and maximum forcing numbers of hexagonal systems
• Disjoint odd cycles in cubic solid bricks
• Extremal anti-forcing numbers of perfect matchings of graphs
• Forcing matchings on square grids
• Global forcing number of benzenoid graphs
• Global forcing number of some chemical graphs
• Hexagonal systems with forcing single edges
• How to build a brick
• scientific article; zbMATH DE number 2152546 (Why is no real title available?)
• scientific article; zbMATH DE number 5238980 (Why is no real title available?)
• Integer and Fractional Matchings
• Matching structure and the matching lattice
• Matching theory
• Maximum forcing number of hexagonal systems
• Maximum matching and a polyhedron with 0,1-vertices
• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• On the anti-forcing number of benzenoids
• On the anti-Kekulé number and anti-forcing number of cata-condensed benzenoids
• On the global forcing number of hexagonal systems
• On the maximum forcing and anti-forcing numbers of (4, 6)-fullerenes
• On two unsolved problems concerning matching covered graphs
• The global forcing number of the parallelogram polyhex
• The minimum forcing number for the torus and hypercube
• The minimum forcing number of perfect matchings in the hypercube
• The perfect matching polytope and solid bricks
• Tight upper bound on the maximum anti-forcing numbers of graphs

Cited in

(7)

• Forcing and anti-forcing edges in bipartite graphs
• Some tight bounds on the minimum and maximum forcing numbers of graphs
• Some novel minimax results for perfect matchings of hexagonal systems
• Tight upper bound on the maximum anti-forcing numbers of graphs
• Complete forcing numbers of complete and almost-complete multipartite graphs
• Complete forcing numbers of (4, 6)-fullerenes
• Forcing, anti-forcing, global forcing and complete forcing on perfect matchings of graphs -- a survey

This page was built for publication: Relations between global forcing number and maximum anti-forcing number of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2078844)