一个 简单图 是某个 简单图 的 线图，当且仅当 它不包含以上九个图中的任何一个作为 禁忌导出子图（van Rooij 和 Wilf 1965；Beineke 1968；Beineke 1970；Skiena 1990，第 138 页；Harary 1994，第 74-75 页；West 2000，第 282 页；Gross 和 Yellen 2006，第 405 页）。这个陈述有时被称为 Beineke 定理。这九个图在 Wolfram 语言 中实现为GraphData["Beineke"]。在这九个图中，一个有四个节点（爪图 = 星图 
= 完全二分图 
），两个有五个节点，六个有六个节点（包括 轮图 
）。
最小 顶点度 至少为 5 的图是线图，当且仅当 它不包含任何六个 Metelsky 图 作为 禁忌导出子图（Metelsky 和 Tyshkevich 1997）。
另请参阅
禁忌导出子图，
线图，
Metelsky 图，
Šoltes 图
使用 Wolfram|Alpha 探索
参考文献
Beineke, L. W. "导出图和有向图。" 收录于 Beiträge zur Graphentheorie (编辑 H. Sachs, H. Voss, 和 H. Walther)。莱比锡，德国：Teubner，第 17-33 页，1968 年。Beineke, L. W. "导出图的特征描述。" J. Combin. Th. 9, 129-135, 1970.Chartrand, G. "关于哈密顿线图。" Trans. Amer. Math. Soc. 134, 559-566, 1968.Gross, J. T. 和 Yellen, J. 图论及其应用，第二版。 Boca Raton, FL: CRC Press, 第 20 和 265 页，2006 年。Harary, F. 图论。 Reading, MA: Addison-Wesley, 1994.Metelsky, Yu. 和 Tyshkevich, R. "关于线性 3-均匀超图的线图。" J. Graph Th. 25, 243-251, 1997.Skiena, S. "线图。" §4.1.5 收录于 实现离散数学：组合数学和图论与 Mathematica。 Reading, MA: Addison-Wesley, 第 128 和 135-139 页，1990 年。van Rooij, A. 和 Wilf, H. "有限图的交换图。" Acta Math. Acad. Sci. Hungar. 16, 263-269, 1965.West, D. B. "线图的特征描述。" 图论导论，第二版。 Englewood Cliffs, NJ: Prentice-Hall, 第 279-282 页，2000 年。
请引用为
Weisstein, Eric W. "Beineke 图。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/BeinekeGraphs.html
主题分类
