主題
Search

Chvátal 圖


ChvatalGraph

Grünbaum 推測,對於每個 m>1n>2,都存在一個 m-正則,m-色圖,其圍長至少為 n。對於 n=2m=2,3,這個結果是顯然的,但僅有少數其他這樣的圖是已知的,包括 12 節點的 Chvátal 圖,21 節點的 Brinkmann 圖,和 25 節點的 Grünbaum 圖。Chvátal 圖在上面的一些嵌入中進行了說明(例如,Bondy;Knuth 2008, p. 39)。

ChvatalGraphLCF

它有 370 個不同的(有向)哈密頓環,給出了唯一的廣義 LCF 記號,階數為 4(如上圖所示),兩個階數為 6(如上圖所示),以及 43 個階數為 1。

Chvátal 圖在 Wolfram 語言 中實現為GraphData["ChvatalGraph"].

Chvátal 圖是一個具有 12 個節點和 24 條邊的四次圖。它的色數為 4,圍長為 4。Chvátal 圖具有圖譜 (-3)^2(1/2(-1-sqrt(17)))^1(-1)^10^21^4(1/2(-1+sqrt(17)))^14^1


另請參閱

Brinkmann 圖, Grünbaum 圖, 四次圖

使用 探索

參考文獻

Bondy, J. A. 和 Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 241, 1976.Grünbaum, B. "A Problem in Graph Coloring." Amer. Math. Monthly 77, 1088-1092, 1970.Knuth, D. E. The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Functions and Boolean Functions.. Upper Saddle River, NJ: Addison-Wesley, 2008.

請引用為

Weisstein, Eric W. "Chvátal Graph." 來自 Web 資源。 https://mathworld.tw/ChvatalGraph.html

主題分類