Anti-forcing spectra of perfect matchings of graphs
Anti-forcing spectra of perfect matchings of graphs
复制标题
图完美匹配的反力谱
DOI：
10.1007/s10878-015-9986-3
复制
发表时间：
2017-02
影响因子：
1
通讯作者：
Zhang Heping
中科院分区：
文献类型：
--
作者：
Deng Kai;Zhang Heping
让我们成为一个图形G的完美匹配。在所得到的子图中，使Mas成为唯一完美匹配的最小数目的边称为Fm的反强迫数。G的反强迫谱是所有完美匹配的反强迫数的集合，由表示。在本文中，我们证明了任何有限正整数集都可以是图的反强迫谱。我们给出了两类反强迫谱为整数区间的六边形系统。最后，我们证明了确定最大度为4的二部图的完美匹配的反强迫数是一个NP-完全问题。
LetMbe a perfect matching of a graphG. The smallest number of edges whose removal to makeMas the unique perfect matching in the resulting subgraph is called the anti-forcing number ofM. The anti-forcing spectrum ofGis the set of anti-forcing numbers of all perfect matchings inG, denoted by. In this paper, we show that any finite set of positive integers can be the anti-forcing spectrum of a graph. We present two classes of hexagonal systems whose anti-forcing spectra are integer intervals. Finally, we show that determining the anti-forcing number of a perfect matching of a bipartite graph with maximum degree four is a NP-complete problem.
登录
查看更多内容
影响因子：
0.9
作者：
N. Biggs
通讯作者：
N. Biggs
DOI：
10.1016/0166-218x(95)00116-9
发表时间：
1997-02
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Xueliang Li
通讯作者：
Xueliang Li
DOI：
--
发表时间：
2009-03
期刊：
Australas. J Comb.
影响因子：
--
作者：
P. Afshani;Hamed Hatami;E. Mahmoodian
通讯作者：
P. Afshani;Hamed Hatami;E. Mahmoodian
影响因子：
3
作者：
D. Klein;M. Randic
通讯作者：
D. Klein;M. Randic
DOI：
--
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Zhongyuan Che;Zhibo Chen
通讯作者：
Zhongyuan Che;Zhibo Chen