タットグラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/09/01 14:55 UTC 版)
| タットグラフ | |
|---|---|
タットグラフ
|
|
| 命名者 | ウィリアム・トーマス・タット |
| 頂点 | 46 |
| 辺 | 69 |
| 半径 | 5 |
| 直径 | 8 |
| 内周 | 4 |
| 自己同型 | 3 (Z/3Z) |
| 彩色数 | 3 |
| 彩色指数 | 3 |
| 特性 | 立方体グラフ 平面グラフ 多面体グラフ |
タットグラフは、46頂点、69辺からなる3-正則グラフであり、W・T・タットにちなんで名付けられた[1]。頂点は3色で彩色可能、3-辺彩色可能であり、内周は4、半径は8である。
タットグラフは立方体グラフであり多面体グラフであるが、ハミルトン路を持たない。したがって、テイト予想の反例である[2]。
1946年にタットはこのテイト予想の反例としてこのグラフを公開した[3]。そして後に、グリンベルクの定理などにより、他の反例も見つかった。
構成
タットは、タットの小片（Tutte fragment）と呼ばれるより小さな構成要素を3つ組み合わせることで、ハミルトン路を持たない多面体グラフを構成した。この小片の飛び出たような辺は「強制的な」辺（＝ハミルトン路の一部に使わなければならない辺）であり、この辺を中心の頂点で3つ連結すると、ハミルトン路はその3つの辺の内2つしか通る事ができない。したがって、タットグラフはハミルトン路を持たない。
組み合わせたグラフは3-正則グラフであり、平面グラフである。したがって、シュタイニッツの定理より、対応する多面体が存在し、その多面体は25個の面を持つ。
この多面体は、四面体から3つの頂点を切り落とすことで幾何学的に実現することができる。4つの大きな面を含む9面からなり、4面のそのうち3つは小片の間に対応し、4つ目は外周に対応する。
代数的な性質
タットグラフの自己同型群は Z/3Z であり、3つの元を持つ巡回群である。
タットグラフの固有多項式は
- タットグラフのページへのリンク
