トゥットグラフ
| トゥットグラフ | |
|---|---|
 トゥットグラフ | |
| 名にちなんで | WTトゥッテ |
| 頂点 | 46 |
| 辺 | 69 |
| 半径 | 5 |
| 直径 | 8 |
| 胴回り | 4 |
| 自己同型 | 3 ( Z /3 Z ) |
| 彩色数 | 3 |
| 彩色指数 | 3 |
| 特性 | 立方 平面 多面体 |
| グラフとパラメータの表 | |
数学のグラフ理論の分野において、タットグラフは、 WTタットにちなんで名付けられた、46の頂点と69の辺を持つ3正則グラフである。[1]彩色数は3 、彩色指数は3、内周は4、直径は8である。
タットグラフは立方 多面体グラフであるが、非ハミルトングラフである。したがって、すべての3次元正多面体はハミルトン閉路を持つというテイトの予想に対する反例となる。 [2]
これは1946年にタットによって発表されたもので、この予想に対して構築された最初の反例である。[3]その後、グリンバーグの定理に基づいた多くの反例が発見された。
建設
WTタットは、タットフラグメントと呼ばれる小さな平面グラフから、3つのフラグメントを組み合わせることで非ハミルトン多面体を構築しました。フラグメントの「必須」辺は、フラグメントを通過するハミルトン経路の一部でなければならず、中心の頂点で接続されています。どの閉路もこれらの3つの辺のうち2つしか使用できないため、ハミルトン閉路は存在しません。
結果として得られるグラフは3連結かつ平面グラフであるため、シュタイニッツの定理によれば多面体のグラフである。25面を持つ。
これは、四面体（その面は図の 4 つの大きな 9 辺の面に対応し、そのうち 3 つは破片のペアの間にあり、4 つ目は外部を形成する）の頂点のうち 3 つを複数切り捨てることで幾何学的に実現できます。
代数的性質
タットグラフの自己同型群はZ /3Zであり、位数3の巡回群である
タットグラフの特性多項式は次の通りである。
関連グラフ
タットグラフは、3元正則非ハミルトン多面体グラフとして初めて発見されましたが、そのようなグラフの中で最小のものではありません
1965年、レーダーバーグは38頂点のバーネット・ボサック・レーダーバーググラフを発見した。 [4] [5] 1968年、グリンバーグはテイトの予想に対する追加の小さな反例として、42、44、46頂点のグリンバーググラフを構築した。[6] 1974年、フォークナーとヤンガーはさらに2つのグラフ、42頂点と44頂点のフォークナー・ヤンガーグラフを発表した。[7]
最後に、ホルトンとマッケイは、38頂点の非ハミルトン多面体で、3辺の切断が非自明な多面体が正確に6個存在することを示しました。これらは、五角柱の頂点のうち2つを、タットの例で使用されたのと同じ断片に置き換えることで形成されます。[8]
参考文献
- ^ Weisstein, Eric W.「Tutteのグラフ」MathWorld
- ^ テイト、PG（1884）、「リストのトポロジー」、哲学雑誌、第5シリーズ、17：30–46Scientific Papers , Vol. II, pp. 85–98に転載。
- ^ Tutte, WT (1946)、「ハミルトン回路について」(PDF)、ロンドン数学会誌、21 (2): 98– 101、doi :10.1112/jlms/s1-21.2.98。
- ^ Lederberg, J. 「DENDRAL-64: 有機分子を木構造と巡回グラフとしてコンピュータで構築、列挙、表記するシステム。第2部 巡回グラフのトポロジー」アメリカ航空宇宙局への中間報告書。Grant NsG 81-60。1965年12月15日。[1]
- ^ ワイスタイン、エリック・W.「バーネット・ボサック・レーダーバーググラフ」。マスワールド。
- ^ Grinberg, EJ「ハミルトン回路を持たない3次平面同次グラフ」ラトビア数学年鑑、Izdat、Zinatne、リガ4、51–58、1968年。
- ^ Faulkner, GBとYounger, DH「非ハミルトン立方平面写像」離散数学7, 67–74, 1974。
- ^ Holton, DA; McKay, BD (1988)、「ハミルトンでない3連結立方平面グラフの最小頂点数は38」、Journal of Combinatorial Theory、シリーズB、45 (3): 305– 319、doi : 10.1016/0095-8956(88)90075-5。
