On the forced matching numbers of bipartite graphs
On the forced matching numbers of bipartite graphs
复制标题
DOI：
10.1016/j.disc.2002.10.002
复制
发表时间：
2004-04
期刊：
影响因子：
--
通讯作者：
Peter Adams;Mohammad Mahdian;E. Mahmoodian
中科院分区：
文献类型：
--
作者：
Peter Adams;Mohammad Mahdian;E. Mahmoodian
设G是一个允许完美匹配的图。G的完美匹配M的一个强制集是M的一个子集S，使得S不包含在G的任何其他完美匹配中。这个概念是在化学中寻找给定分子的共振结构的研究中出现的。类似的概念已经在定义集的名称下研究了块设计和图形着色，以及在临界集的名称下研究了拉丁方。在化学的背景下，有一些关于六角系统的强迫集的研究，但只有少数其他类别的图被考虑过。对于超立方体Qn，这是一个非常有趣的概念，其中包括许多具有挑战性的问题。本文研究了求图的强制数的计算复杂性，给出了超立方体Qn的不同匹配的强制数的可能值的一些结果。此外，我们展示了一个应用程序的临界集后循环拉丁矩形。
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 has arisen in the study of finding resonance structures of a given molecule in chemistry. Similar concepts have been studied for block designs and graph colorings under the name defining set, and for Latin squares under the name critical set. There is some study of forcing sets of hexagonal systems in the context of chemistry, but only a few other classes of graphs have been considered. For the hypercubes Qn, it turns out to be a very interesting notion which includes many challenging problems. In this paper we study the computational complexity of finding the forcing number of graphs, and we give some results on the possible values of forcing number for different matchings of the hypercube Qn. Also we show an application to critical sets in back circulant Latin rectangles.