一個 簡單圖 是某個 簡單圖 的 線圖，當且僅當 它不包含以上九個圖中的任何一個作為 禁忌匯出子圖（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 圖
使用 探索
參考文獻
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 圖。" 來自 —— 資源。 https://mathworld.tw/BeinekeGraphs.html
主題分類
