| メレディスグラフ | |
|---|---|
 メレディスグラフ | |
| 名前の由来 | GHメレディス |
| 頂点 | 70 |
| エッジ | 140 |
| 半径 | 7 |
| 直径 | 8 |
| 胴回り | 4 |
| 自己同型 | 38698352640 |
| 彩色数 | 3 |
| 色指数 | 5 |
| 本の厚さ | 3 |
| キュー番号 | 2 |
| プロパティ | オイラー |
| グラフとパラメータの表 | |
数学のグラフ理論の分野において、メレディスグラフは、 1973年にガイ・H・J・メレディスによって発見された70頂点140辺の4正則 無向グラフである。[1]
メレディスグラフは4頂点連結、4辺連結で、彩色数は3、彩色指数は5、半径は7、直径は8、胴回りは4、非ハミルトングラフである。[2]本の厚さは3、待ち行列数は2である。 [3]
1973年に発表されたこの論文は、すべての4正則4頂点連結グラフはハミルトングラフであるというクリスピン・ナッシュ＝ウィリアムズ予想に対する反例を提供している。 [4] [5]しかし、WTタットはすべての4連結平面グラフがハミルトングラフであることを示した。 [ 6]
メレディスグラフの特性多項式は です。
ギャラリー
参考文献
- ^ Weisstein, Eric W.「メレディスグラフ」。MathWorld。
- ^ Bondy, JAとMurty, USR「グラフ理論」Springer、p. 470、2007年。
- ^ ジェシカ・ウォルツ、「SATを用いた線形レイアウトのエンジニアリング」。修士論文、テュービンゲン大学、2018年
- ^ Meredith, GHJ (1973). 「正則n価n連結非ハミルトン非n辺彩色グラフ」. Journal of Combinatorial Theory, Series B. 14 : 55–60 . doi : 10.1016 /s0095-8956(73)80006-1 . MR 0311503.
- ^ Bondy, JA、Murty, USR「グラフ理論とその応用」ニューヨーク：ノースホランド、239ページ、1976年。
- ^ Tutte, WT編『組合せ論の最近の進歩』Academic Press, New York, 1969年。
