• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of combinatorial optimization >Anti-forcing spectra of perfect matchings of graphs
【24h】

Anti-forcing spectra of perfect matchings of graphs

机译：图形完美匹配的反强制谱

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Let M be a perfect matching of a graph G. The smallest number of edges whose removal to make M as the unique perfect matching in the resulting subgraph is called the anti-forcing number of M. The anti-forcing spectrum of G is the set of anti-forcing numbers of all perfect matchings in G, 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.
机译：让M成为图表G.最小数量的边缘的完美匹配，其删除是由所得到的子图中的独特完美匹配称为M. G的反迫使频谱是集合 G的所有完美匹配的反矫正数量表示。 在本文中，我们表明，任何有限的正整数都可以是图形的反强制频谱。 我们提出了两类六边形系统，其防伪光谱是整数间隔。 最后，我们表明，确定具有最大四个具有最大四个的双链图的完美匹配数是NP完整问题。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号