Loading article…
| トゥッテグラフ | |
|---|---|
 トゥッテグラフ | |
| 名前の由来 | WT トゥッテ |
| 頂点 | 46 |
| エッジ | 69 |
| 半径 | 5 |
| 直径 | 8 |
| 胴回り | 4 |
| 自己同型 | 3 ( Z /3 Z ) |
| 彩度数 | 3 |
| 色指数 | 3 |
| プロパティ | 立方 平面 多面体 |
| グラフとパラメータの表 | |
数学のグラフ理論の分野において、タットグラフは、 WTタットにちなんで名付けられた46頂点69辺を持つ3正則グラフである。[1]彩色数は3、彩色指数は3、胴回りは4、直径は8である。
タットグラフは3次 多面体グラフですが、非ハミルトングラフです。したがって、すべての3次正多面体はハミルトン閉路を持つというテイトの予想に対する反例です。 [2]
これは1946年にタットによって発表されたもので、この予想に対して構築された最初の反例である。[3]その後、他の反例が発見されたが、その多くはグリンバーグの定理に基づいていた。
工事
WT タットは、タットフラグメントと呼ばれる小さな平面グラフから、3 つのフラグメントを組み合わせて非ハミルトン多面体を構築しました。フラグメントの「必須」エッジは、フラグメントを通過するすべてのハミルトン経路の一部でなければなりませんが、中央の頂点で接続されています。どのサイクルでもこれらの 3 つのエッジのうち 2 つしか使用できないため、ハミルトンサイクルは存在しません。
結果として得られるグラフは3 連結かつ平面であるため、シュタイニッツの定理によれば多面体のグラフになります。25 の面があります。
これは、四面体（その面は図の 4 つの大きな 9 面に対応し、そのうち 3 つは破片のペアの間にあり、4 つ目は外部を形成する）の頂点のうち 3 つを複数切り捨てることで幾何学的に実現できます。
代数的性質
タットグラフの自己同型群はZ /3 Zであり、これは位数 3 の巡回群である。
タットグラフの 特性多項式は次の通りである。
関連グラフ
タットグラフは、発見された最初の 3 正則非ハミルトン多面体グラフですが、そのようなグラフの中で最小のものではありません。
1965年、レーダーバーグは38頂点のバーネット・ボサック・レーダーバーググラフを発見した。[4] [5] 1968年、グリンバーグはテイトの予想に対するさらなる小さな反例として、42、44、46頂点のグリンバーググラフを構築した。[6] 1974年、フォークナーとヤンガーはさらに2つのグラフ、42頂点と44頂点のフォークナー・ヤンガーグラフを発表した。[7]
最後にホルトンとマッケイは、38頂点の非ハミルトン多面体で、3辺の切断が非自明なものが6つあることを示した。これらは、五角柱の頂点のうち2つをタットの例で使用されたのと同じ断片に置き換えることで形成される。[8]
参考文献
- ^ ワイスタイン、エリック W.「トゥッテのグラフ」。マスワールド。
- ^ テイト、PG（1884）、「リストのトポロジー」、哲学雑誌、第5シリーズ、17：30–46. Scientific Papers、第2巻、pp.85-98に再掲載。
- ^ Tutte, WT (1946)、「ハミルトン回路について」(PDF)、ロンドン数学会誌、21 (2): 98–101、doi :10.1112/jlms/s1-21.2.98。
- ^ Lederberg, J. 「DENDRAL-64: 有機分子をツリー構造と循環グラフとしてコンピュータで構築、列挙、表記するシステム。パート II. 循環グラフのトポロジー。」アメリカ航空宇宙局への中間報告書。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。