Extremal anti-forcing numbers of perfect matchings of graphs

DOI10.1016/J.DAM.2017.02.024MaRDI QIDQ526817zbMATH OpenOpenAlexFDO

Authors Kai Deng, Heping Zhang

Publication date 15 May 2017

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

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

zbMATH Keywords

anti-forcing numberanti-forcing spectrumcyclomatic numberelementary bipartite grapheven polygonal chainperfect matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The anti-forcing number of a perfect matching $M$ of a graph $G$ is the minimal number of edges not in $M$ whose removal to make $M$ as a unique perfect matching of the resulting graph. The set of anti-forcing numbers of all perfect matchings of $G$ is the anti-forcing spectrum of $G$. In this paper, we characterize the plane elementary bipartite graph whose minimum anti-forcing number is one. We show that the maximum anti-forcing number of a graph is at most its cyclomatic number. In particular, we characterize the graphs with the maximum anti-forcing number achieving the upper bound, such extremal graphs are a class of plane bipartite graphs. Finally, we determine the anti-forcing spectrum of an even polygonal chain in linear time.

Recommendations

• Anti-forcing numbers of perfect matchings of graphs
• Anti-forcing spectra of perfect matchings of graphs
• Tight upper bound on the maximum anti-forcing numbers of graphs
• The anti-forcing number of double hexagonal chains
• The anti-forcing number of hexagonal chains

Cites work

• Anti-forcing numbers of perfect matchings of graphs
• Anti-forcing spectra of perfect matchings of graphs
• Anti-forcing spectrum of any cata-condensed hexagonal system is continuous
• Defining sets in vertex colorings of graphs and latin rectangles
• Forcing matching numbers of fullerene graphs
• Forcing matchings on square grids
• Hexagonal systems with forcing edges
• Hexagonal systems with forcing single edges
• scientific article; zbMATH DE number 6127683 (Why is no real title available?)
• scientific article; zbMATH DE number 6749523 (Why is no real title available?)
• Matching theory
• On forcing matching number of boron-nitrogen fullerene graphs
• On minimal elementary bipartite graphs
• On the anti-forcing number of benzenoids
• On the anti-Kekulé and anti-forcing number of cata-condensed phenylenes
• On the anti-Kekulé number and anti-forcing number of cata-condensed benzenoids
• On the forced matching numbers of bipartite graphs
• On the spectrum of the forced matching number of graphs
• Plane elementary bipartite graphs
• The anti-forcing number of double hexagonal chains
• The anti-forcing number of hexagonal chains
• The forcing number of toroidal polyhexes
• The maximum forcing number of cylindrical grid, toroidal 4-8 lattice and Klein bottle 4-8 lattice
• The minimum forcing number for the torus and hypercube

Cited in

(23)

• Anti-forcing spectrum of any cata-condensed hexagonal system is continuous
• Extremal hypergraphs for matching number and domination number
• Forcing and anti-forcing polynomials of perfect matchings for some rectangle grids
• Forcing and anti-forcing edges in bipartite graphs
• Anti-forcing polynomials for benzenoid systems with forcing edges
• Plane elementary bipartite graphs with forcing or anti-forcing edges
• Relations between global forcing number and maximum anti-forcing number of a graph
• Some tight bounds on the minimum and maximum forcing numbers of graphs
• The anti-forcing spectra of \(( 4 , 6 )\)-fullerenes
• Some novel minimax results for perfect matchings of hexagonal systems
• Forcing and anti-forcing polynomials of a type of polyomino graphs
• The anti-forcing number of double hexagonal chains
• Tight upper bound on the maximum anti-forcing numbers of graphs
• Anti-forcing number of some specific graphs
• scientific article; zbMATH DE number 7339006 (Why is no real title available?)
• scientific article; zbMATH DE number 7339206 (Why is no real title available?)
• Computing the forcing and anti-forcing numbers of perfect matchings for graphs by integer linear programmings
• Anti-forcing spectra of perfect matchings of graphs
• Anti-forcing numbers of perfect matchings of graphs
• Maximizing the minimum and maximum forcing numbers of perfect matchings of graphs
• Fractional forcing number of graphs
• Forcing, anti-forcing, global forcing and complete forcing on perfect matchings of graphs -- a survey
• The anti-Ramsey number of perfect matching

This page was built for publication: Extremal anti-forcing numbers of perfect matchings of graphs

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