“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 2343
School of Mathematics
  Title:   On the spectrum of the forced matching number of graphs
1.  P. Afshani
2.  H. Hatami
3.  E. S. Mahmoodian
  Status:   Published
  Journal: Australas. J. Combin.
  Vol.:  30
  Year:  2004
  Pages:   147-160
  Supported by:  IPM
Let G be a graph that admits a perfect matching. A 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 coloring under the name defining set, and for Latin squares under the name 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 matching 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 Pm ×Pn, 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.

Download TeX format
back to top
scroll left or right