On the spectrum of the forced matching number of graphs

zbMATH Open1056.05110arXiv0903.2578MaRDI QIDQ4820537FDOQ4820537

Authors: Peyman Afshani, Hamed Hatami, E. S. Mahmoodian 

Publication date: 15 October 2004

Abstract: Let $G$ be a graph that admits a perfect matching. A {sf forcing set} for a perfect matching $M$ of $G$ is a subset $S$ of $M$, such that $S$ is contained in no other perfect matching of $G$. This notion originally arose in chemistry in the study of molecular resonance structures. Similar concepts have been studied for block designs and graph colorings under the name {sf defining set}, and for Latin squares under the name {sf critical set}. Recently several papers have appeared on the study of forcing sets for other graph theoretic concepts such as dominating sets, orientations, and geodetics. Whilst there has been some study of forcing sets of matchings of hexagonal systems in the context of chemistry, only a few other classes of graphs have been considered. Here we study the spectrum of possible forced matching numbers for the grids $P_{m}imes{P}_n$, discuss the concept of a forcing set for some other specific classes of graphs, and show that the problem of finding the smallest forcing number of graphs is NP--complete.

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

Recommendations

• Forcing matchings on square grids
• Continuous forcing spectra of even polygonal chains
• Maximizing the minimum and maximum forcing numbers of perfect matchings of graphs
• The maximum forcing number of cylindrical grid, toroidal 4-8 lattice and Klein bottle 4-8 lattice
• Anti-forcing spectra of perfect matchings of graphs

zbMATH Keywords

matchingforced matching number

Mathematics Subject Classification ID

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

Cited In (31)

• A Sufficient and Necessary Condition for the Forcing Number of a Bipartite Graph Being Equal to the Minimum Number of Trailing Vertices
• Computing the forcing and anti-forcing numbers of perfect matchings for graphs by integer linear programmings
• A minimax result for perfect matchings of a polyomino graph
• The maximum forcing number of cylindrical grid, toroidal 4-8 lattice and Klein bottle 4-8 lattice
• On the spectrum of the perfect matching derangement graph
• Anti-forcing spectrum of any cata-condensed hexagonal system is continuous
• Title not available (Why is that?)
• Title not available (Why is that?)
• On forcing matching number of boron-nitrogen fullerene graphs
• Continuous forcing spectra of even polygonal chains
• Forcing matching numbers of fullerene graphs
• Continuous forcing spectrum of regular hexagonal polyhexes
• Forcing matchings on square grids
• Forcing numbers of stop signs.
• On the computational complexity of defining sets
• Title not available (Why is that?)
• Complete forcing numbers of primitive coronoids
• On the forced matching numbers of bipartite graphs
• Complete forcing numbers of catacondensed hexagonal systems
• Forcing and anti-forcing polynomials of a type of polyomino graphs
• On the forcing matching numbers of prisms of graphs
• Anti-forcing spectra of perfect matchings of graphs
• Extremal anti-forcing numbers of perfect matchings of graphs
• Bounds and monotonicity of critical set parameters of colourings
• 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
• On the maximum forcing and anti-forcing numbers of \((4, 6)\)-fullerenes
• Forcing and anti-forcing polynomials of perfect matchings for some rectangle grids
• Global forcing number for maximal matchings

This page was built for publication: On the spectrum of the forced matching number of graphs

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