Extremal anti-forcing numbers of perfect matchings of graphs

DOI10.1016/J.DAM.2017.02.024zbMATH Open1361.05100arXiv1607.05392OpenAlexW2964206588MaRDI QIDQ526817FDOQ526817

Authors: Kai Deng, Heping Zhang 

Publication date: 15 May 2017

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

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.

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

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

zbMATH Keywords

perfect matchingcyclomatic numberanti-forcing numberanti-forcing spectrumelementary bipartite grapheven polygonal chain

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (21)

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

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)