On the spectrum of the forced matching number of graphs
On the spectrum of the forced matching number of graphs
复制标题
DOI：
--
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
P. Afshani;Hamed Hatami;E. Mahmoodian
中科院分区：
文献类型：
--
作者：
P. Afshani;Hamed Hatami;E. Mahmoodian
令 $G$ 为允许完美匹配的图。 $G$ 的完美匹配 $M$ 的 {\sf 强制集} 是 $M$ 的子集 $S$，使得 $S$ 不包含在 $G$ 的其他完美匹配中。这个概念最初出现在化学中分子共振结构的研究中。类似的概念已经被研究用于名为 {\sf 定义集} 的块设计和图形着色，以及名为 {\sf 临界集} 的拉丁方。最近出现了几篇关于其他图论概念（例如支配集、方向和大地测量学）的强制集研究的论文。虽然已经有一些在化学背景下强制六方系统匹配组的研究，但只考虑了其他几类图。在这里，我们研究了网格 $P_m \times P_n$ 可能的强制匹配数的范围，讨论了其他一些特定类图的强制集的概念，并表明寻找图的最小强制数的问题是 \NP--complete 的。
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 \times 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.