Extremal anti-forcing numbers of perfect matchings of graphs
Extremal anti-forcing numbers of perfect matchings of graphs
复制标题
图完美匹配的极值反强迫数
DOI：
10.1016/j.dam.2017.02.024
复制
发表时间：
2016-07
影响因子：
1.1
通讯作者：
Zhang Heping
中科院分区：
文献类型：
--
作者：
Deng Kai;Zhang Heping
图G的完美匹配M的反强迫数是不属于M的边的最小数目，移除这些边使M成为最终图的唯一完美匹配。G的所有完美匹配的反强迫数的集合就是G的反强迫谱。本文刻画了最小反强迫数为1的平面初等二部图。我们证明了图的最大反强迫数至多是它的圈数。特别地，我们刻画了最大反强迫数达到上界的图，这种极值图是平面二部图的一类。最后，我们确定了偶多边形链在线性时间内的反强迫谱。
The anti-forcing number of a perfect matching M of a graph G is the minimal number of edges not in M whose removal to make M as a unique perfect matching of the resulting graph. The set of anti-forcing numbers of all perfect matchings of G is the anti-forcing spectrum of G. In this paper, we characterize the plane elementary bipartite graph whose minimum anti-forcing number is one. We show that the maximum anti-forcing number of a graph is at most its cyclomatic number. In particular, we characterize the graphs with the maximum anti-forcing number achieving the upper bound, such extremal graphs are a class of plane bipartite graphs. Finally, we determine the anti-forcing spectrum of an even polygonal chain in linear time.
登录
查看更多内容
DOI：
10.1016/0166-218x(95)00116-9
发表时间：
1997-02
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Xueliang Li
通讯作者：
Xueliang Li
影响因子：
--
作者：
Deng Kai;Zhang Heping
通讯作者：
Zhang Heping
DOI：
--
发表时间：
2007
期刊：
--
影响因子：
--
作者：
H. Deng
通讯作者：
H. Deng
影响因子：
1
作者：
Deng Kai;Zhang Heping
通讯作者：
Zhang Heping
DOI：
--
发表时间：
2009-03
期刊：
Australas. J Comb.
影响因子：
--
作者：
P. Afshani;Hamed Hatami;E. Mahmoodian
通讯作者：
P. Afshani;Hamed Hatami;E. Mahmoodian