タットグラフ

タットグラフは、46頂点、69辺からなる3-正則グラフであり、W・T・タットにちなんで名付けられたWeisstein, Eric W. "Tutte's Graph". MathWorld.。頂点は3色で彩色可能、3-辺彩色可能であり、内周は4、半径は8である。

タットグラフは立方体グラフであり多面体グラフであるが、ハミルトン路を持たない。したがって、テイト予想の反例である. Reprinted in Scientific Papers, Vol. II, pp. 85–98.。

1946年にタットはこのテイト予想の反例としてこのグラフを公開した.。そして後に、グリンベルクの定理などにより、他の反例も見つかった。

 構成 
左|サムネイル|165x165ピクセル|タットの小片
タットは、タットの小片（Tutte fragment）と呼ばれるより小さな構成要素を3つ組み合わせることで、ハミルトン路を持たない多面体グラフを構成した。この小片の飛び出たような辺は「強制的な」辺（＝ハミルトン路の一部に使わなければならない辺）であり、この辺を中心の頂点で3つ連結すると、ハミルトン路はその3つの辺の内2つしか通ることができない。したがって、タットグラフはハミルトン路を持たない。

組み合わせたグラフは3-正則グラフであり、平面グラフである。したがって、シュタイニッツの定理より、対応する多面体が存在し、その多面体は25個の面を持つ。

この多面体は、四面体から3つの頂点を切り落とすことで幾何学的に実現することができる。4つの大きな面を含む9面からなり、4面のそのうち3つは小片の間に対応し、4つ目は外周に対応する。

 代数的な性質 
タットグラフの自己同型群は Z/3Z であり、3つの元を持つ巡回群である。

タットグラフの固有多項式は


である。

 関連するグラフ 
タットグラフは1946年に発見された3-正則グラフであり、最初にハミルトン路が存在しないことが知られたグラフであるが、そのような性質を持つグラフの中で最小のグラフではない。

1965年にレーダーバーグは38頂点の Barnette–Bosák–Lederberg グラフを発見したLederberg, J. "DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs." Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. .Weisstein, Eric W. "Barnette-Bosák-Lederberg Graph". MathWorld.。1968年には、グリンベルクがテイト予想の反例として42、44、46頂点のグリンベルクグラフを追加したGrinberg, E. J. "Plane Homogeneous Graphs of Degree Three without Hamiltonian Circuits." Latvian Math. Yearbook, Izdat. Zinatne, Riga 4, 51–58, 1968.。1974年には、フォークナーとヤンガーは42頂点と44頂点の反例を発見したFaulkner, G. B. and Younger, D. H. "Non-Hamiltonian Cubic Planar Maps." Discrete Math. 7, 67–74, 1974.。

そして1988年に、ホルトンとマッケイは6種類の38頂点からなるハミルトン路を持たない多面体を見つけた。それらは五角柱の2つの頂点をタットの小片に置き換えたものからなる.。

 出典 

Category:数学に関する記事