“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 2343 |
|
||||||
| Abstract: | |||||||
|
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 | |||||||
