主題
Search

Tutte 8-籠


LeviGraph

Tutte 8-籠(Godsil 和 Royle 2001, p. 59;右圖)是一個三次圖,具有 30 個節點和 45 條邊,它是 Levi 圖Cremona-Richmond 構型。它由上面說明的最左邊兩個子圖的並集組成。Tutte 8-籠是唯一的 (3,8)-籠圖Moore 圖。它也是一個 廣義多邊形,是廣義四邊形 W_2 的點/線 Levi 圖,其 線圖廣義八邊形 GO(2,1)。該圖最早由 Tutte (1947) 發現,也稱為 Tutte-Coxeter 圖(Bondy 和 Murty 1976, p. 237;Brouwer et al. 1989, p. 209)或 Tutte 籠(Read 和 Wilson 1998, p. 271)。

LeviGraphEmbeddings

上面展示了 Tutte 8-籠的多種嵌入方式。

Tutte 8-籠圖的直線交叉數是 13,這是由 G. Exoo 在 1990 年左右確定的(G. Exoo,私人通訊,2019 年 5 月 12 日)。它是已知的圖交叉數為 13 的最小三次圖,這使其很可能成為最小三次交叉數圖,儘管截至 2019 年 5 月,這一點尚未最終確定(Pegg 和 Exoo 2009, Clancy et al. 2019)。

它是 4-弧傳遞的,圍長為 8,直徑為 4,色數為 2,自同構群階數為 1440。它也是距離正則距離傳遞的,具有相交陣列 {3,2,2,2;1,1,1,3}。Tutte 8-籠圖是一個積分圖,其圖譜(-3)^1(-2)^90^(10)2^93^1。它可以 LCF 符號表示為 [-13,-9,7,-7,9,13]^5 (Frucht 1976)。

LeviGraphUnitDistance

它也是一個單位距離圖(Gerbracht 2008),如上所示,在多個單位距離嵌入中進行了說明(E. Gerbracht,私人通訊,2010 年 1 月)。

Tutte 8-籠在 Wolfram 語言中實現為GraphData["Tutte8Cage"].


另請參閱

籠圖, 構型, 積分圖, Moore 圖, 最小三次交叉數圖, Tutte 12-籠

使用 探索

參考文獻

Bondy, J. A. and Murty, U. S. R. 圖論及其應用。 New York: North Holland, pp. 237 and 276, 1976.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. 距離正則圖。 New York: Springer-Verlag, p. 209, 1989.Clancy, K.; Haythorpe, M.; Newcombe, A.; and Pegg, E. Jr. "不存在頂點數為 26 且交叉數為 10 或 11 的三次圖。" Preprint. 2019.Coxeter, H. S. M. "自對偶構型和正則圖。" Bull. Amer. Math. Soc. 56, 413-455, 1950.Coxeter, H. S. M. "PG(3,3) 中非直紋二次曲面的弦。" Canad. J. Math. 10, 484-488, 1958.Coxeter, H. S. M. "PG(5,3) 中具有 95040 個自變換的十二個點。" Proc. Roy. Soc. London Ser. A 247, 279-293, 1958.DistanceRegular.org. "Tutte 的 8-籠。" http://www.distanceregular.org/graphs/tutte8.html.Exoo, G. "著名圖的直線圖:Tutte 8-籠。" http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/tutte.gif.Frucht, R. "三價哈密頓圖的規範表示。" J. Graph Th. 1, 45-60, 1976.Gerbracht, E. H.-A. "關於連通三次對稱圖的單位距離可嵌入性。" Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.Godsil, C. and Royle, G. 代數圖論。 New York: Springer-Verlag, 2001.Harary, F. 圖論。 Reading, MA: Addison-Wesley, pp. 174-175, 1994.Pegg, E. Jr. and Exoo, G. "交叉數圖。" Mathematica J. 11, 161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.Pisanski, T. and Randić, M. "幾何與圖論之間的橋樑。" In 工作中的幾何:展示幾何應用論文集 (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Read, R. C. and Wilson, R. J. 圖譜。 Oxford, England: Oxford University Press, p. 271, 1998.更新連結Royle, G. "F030A." http://www.csse.uwa.edu.au/~gordon/foster/F030A.html更新連結Royle, G. "三次籠。" http://school.maths.uwa.edu.au/~gordon/remote/cages/Tutte, W. T. "一族立方圖。" Proc. Cambridge Philos. Soc., 459-474, 1947.Tutte, W. T. 圖的連通性。 Toronto, Ontario: University of Toronto Press, 1966.Tutte, W. T. "PG(3,3) 中非直紋二次曲面的弦。" Canad. J. Math. 10, 481-483, 1958.Wong, P. K. "籠--綜述。" J. Graph Th. 6, 1-22, 1982.

請引用為

Weisstein, Eric W. "Tutte 8-籠。" 來自 Web 資源。 https://mathworld.tw/Tutte8-Cage.html

主題分類