The maximum forcing number of cylindrical grid, toroidal 4-8 lattice and Klein bottle 4-8 lattice
The maximum forcing number of cylindrical grid, toroidal 4-8 lattice and Klein bottle 4-8 lattice
复制标题
圆柱格、环形4-8格、克莱因瓶4-8格最大受力数
DOI：
10.1007/s10910-015-0541-3
复制
发表时间：
2016
影响因子：
1.7
通讯作者：
Zhang Heping
中科院分区：
文献类型：
--
作者：
Jiang Xiaoyan;Zhang Heping
让我们给出一个允许完美匹配的图。完美匹配MofG的一个强制集是子集SofM，使得Sf不包含在G的其他完美匹配中。M的强制集的最小基数称为强制匹配数，记为f(G，M)。在G的所有完美匹配中，最大强制匹配数称为G的最大强制匹配数，记为f(G)。在本文中，我们通过选择合适的独立图集来证明柱面网格的最大强迫数。这解决了Afshani等人提出的一个悬而未决的问题。(澳大利亚J Combin 30：147-160,2004)。此外，我们还得到了两类环形4-8格子和两类Klein瓶状4-8格子的最大强迫数都等于平方响应数。
LetGbe a graph that admits a perfect matching. A forcing set for a perfect matchingMofGis a subsetSofM, such thatSis contained in no other perfect matchings ofG. The smallest cardinality of a forcing set ofMis called forced matching number, denoted byf(G,M). Among all perfect matchings ofG, the maximum forcing matching number is called the maximum forcing number ofG, denoted byF(G). In this paper, we show that the maximum forcing numbers of cylindrical gridisby choosing a suitable independent set of this graph. This solves an open problem proposed by Afshani et al. (Australas J Combin 30:147–160, 2004). Moreover, we obtain that the maximum forcing numbers of two classes of toroidal 4–8 lattice and two classes of Klein bottle 4–8 lattice are all equal to the number of squarespq.