主题
Search

无爪图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
Claw

一个图是无爪图 当且仅当 它不包含 完全二部图 K_(1,3) (被称为“爪图”；如上图所示) 作为 禁用导出子图。

任何图的线图都是无爪图，任何无三角形图的补图也是如此。

无爪图的图类包括

1. 反棱柱图,

2. 哑铃图,

3. 主教图 (及其连通分量),

4. 鸡尾酒会图 K_(n×2),

5. 完全图,

6. 环图,

7. 德布鲁因图,

8. 空图 K^__n,

9. 河内图,

10. 梯子横档图,

11. 车图,

12. 线图,

13. 棒棒糖图,

14. 路径图 P_n,

15. 谢尔宾斯基垫片图,

16. 强完美图,

17. 三角图, 和

18. 2-正则图。

Claw-FreeGraphs

n 个节点上无爪简单图的数量，对于 n 节点，当 n=1, 2, ... 分别是 1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... (OEIS A086991; 如上图所示)。

ConnectedClaw-FreeGraphs

n 个节点上无爪连通简单图的数量，对于 n 节点，当 n=1, 2, ... 分别是 1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, 1728403, ... (OEIS A022562; 如上图所示)。

Minty (1980) 证明了 最大独立集问题，该问题在无限制图上通常是 NP-完全 的，但在无爪图上可以用强多项式时间解决。他的证明使用了 Edmonds (1965) 的算法来找到最大权重匹配。然而，Nakamura 和 Tamura (2001) 表明该算法在某些特殊情况下会失败，并提供了修改来纠正这个错误。在无爪图中找到最大基数独立集的问题由 Sbihi (1980) 解决。

另请参阅

爪图, 完全二部图, 禁用导出子图, 线图, 完美匹配

此条目的部分内容由 Jonathan William Mugan 贡献

使用 探索

参考文献

Edmonds, J. "Paths, Trees, and Flowers." Canad. J. Math. 17, 449-467, 1965.Faudree, R.; Flandrin, E.; and Ryjáček, Z. "Claw-Free Graphs--A Survey." Disc. Math. 164, 87-147, 1997.Minty, G. J. "On Maximal Independent Sets of Vertices in Claw Free Graphs." J. Combin. Th. B 28, 284-304, 1980.Nakamura, D. and Tamura, A. "A Revision of Minty's Algorithm for Finding a Maximum Weight Stable Set of a Claw-Free Graph." J. Oper. Res. Soc. Japan 44, 194-204, 2001.Sbihi, N. "Algorithme de Recherche d'un Stable de Cardinalite Maximum dans un Graphe sans Étoile." Disc. Math. 29, 53-76, 1980.Sloane, N. J. A. Sequences A022562 and A086991 in "The On-Line Encyclopedia of Integer Sequences."

在 中引用

无爪图

请引用为

Mugan, Jonathan William 和 Weisstein, Eric W. "Claw-Free Graph." 来自 —— 资源。 https://mathworld.net.cn/Claw-FreeGraph.html

学科分类