ハーシェルグラフ

ハーシェルグラフ
ハーシェルグラフ
	ハーシェルグラフ。
名前の由来	アレクサンダー・スチュワート・ハーシェル
頂点	11
エッジ	18
自己同型	12 ( D 6 )
プロパティ	多面体; 二分法; 非ハミルトン;
	グラフとパラメータの表

数学の一分野であるグラフ理論において、ハーシェルグラフは、 11 個の頂点と 18 個の辺を持つ2 部無向グラフである。これは多面体グラフ(凸多面体のグラフ) であり、すべての頂点を通過する閉路であるハミルトン閉路を持たない最小の多面体グラフである。このグラフは、イギリスの天文学者アレクサンダー・スチュワート・ハーシェルにちなんで名付けられている。これは、ハーシェルが多面体グラフのハミルトン閉路を研究したためである (ただし、このグラフのハミルトン閉路は研究していない)。

定義と特性

ハーシェルグラフには、4 次頂点が 3 つ (図の中央で垂直に並んだ 3 つの青い頂点) と 3 次頂点が 8 つあります。4 次頂点はそれぞれ 2 つあり、3 次頂点が 2 つ隣接しており、これらの隣接頂点と 4 頂点サイクルを形成しています。このサイクルは 3 つあり、8 つの 3 次頂点 (図では赤) のうち 6 つを通過します。さらに 2 つの 3 次頂点 (青) は、これらの 4 頂点サイクルには参加していません。代わりに、それぞれが 6 つの赤い頂点のうち 3 つに隣接しています。^[1]

ハーシェルグラフは多面体グラフです。つまり、平面グラフであり、平面上にどの辺も交差することなく描くことができ、3頂点連結です。つまり、任意の2つの頂点を削除すると連結されたサブグラフが残ります。 [ ^1]これは2部グラフです。図示のように、5つの青い頂点と6つの赤い頂点で色付けされている場合、各辺には赤い端点と青い端点が1つずつあります。^[2]

この多様体は6次の二面体対称性を持ち、自己同型群の要素は合計12個である。4次の頂点は任意に並べ替えることができ、6通りの並べ替えが可能で、さらに4次の頂点の各並べ替えに対して、これらの頂点を固定したまま3次の頂点のペアを交換する対称性が存在する。^[1]

多面体

シュタイニッツの定理によれば、平面で3頂点連結なグラフはすべて、そのグラフを骨格とする凸多面体を持つ。^[3]ハーシェルグラフはこれらの性質を持つため、^[1]次のように凸多面体で表すことができる。つまり、多面体は9つの四辺形を面として持つ。^{[4]これは、各}グラフの自己同型性が多面体の対称性に対応するように選択することができ、その場合、3つの面は菱形または正方形になり、他の6つの面は凧形になる。^[1]

二重多面体は、三角柱の辺の中点の凸包として形成できる、平行三角柱です。このように構築すると、三角柱の正方形の面と同じ平面に 3 つの正方形の面、三角柱の両端の平面に 2 つの正三角形の面、および 6 つの二等辺三角形の面があります。この多面体には、連続した数字が隣接する面に現れるように、また最初と最後の数字も隣接する面になるように面を番号付けすることができないという特性があります。これは、そのような番号付けは、必然的にハーシェルグラフのハミルトンサイクルに対応するためです。このタイプの多面体面の番号付けは、マジック: ザギャザリングゲームで「スピンダウンライフカウンター」として使用され、ライフが失われるたびに多面体を隣接する面に向けることで、プレイヤーのライフを追跡します。ゲーム内のカード「リッチ」は、プレイヤーがライフが1つしかないほぼ失われた状態から、最初のライフ数まで戻すことを可能にする。ハーシェルグラフの双対多面体は、このステップで隣接する面を接続するような方法で番号を付けることはできないため、コンスタンティニデスとコンスタンティニデス（2018）は、この双対多面体の標準的な多面体実現を「リッチの宿敵」と名付けた。^[5]

ハミルトン性

ハーシェルグラフは奇数の頂点を持つ二部グラフなので、ハミルトン閉路（各頂点を正確に 1 回通過する辺の閉路）は含まれません。なぜなら、どの二部グラフでも、閉路は二分割の両側の頂点の間で交互に存在しなければならないため、両方の種類の頂点が同数含まれ、長さが偶数でなければなりません。したがって、11 個の頂点のそれぞれを 1 回通過する閉路は、ハーシェルグラフには存在できません。ハミルトン閉路を含むグラフはハミルトングラフと呼ばれるため、ハーシェルグラフはハミルトングラフではありません。ハーシェルグラフは、非ハミルトン多面体グラフの中で、頂点数、辺数、面数が最も少ないグラフです。^[6] 11 個の頂点を持ち、ハミルトン閉路を持たない多面体グラフは他にも存在しますが（特にゴールドナー・ハラリーグラフ）、 ^[7]、これより辺数が少ないグラフはありません。^[6]

ハーシェルグラフの頂点のうち3つを除くすべての頂点の次数は3である。すべての頂点の次数が3であるグラフは、立方グラフまたは3正則グラフと呼ばれる。PGテイトは、多面体の3正則グラフはハミルトングラフでなければならないと予想した^{[8] 。これは、}WT タットが反例であるタットグラフを提示したことで反証された。タットグラフはハーシェルグラフよりもはるかに大きい。^[9]テイトの予想を改良した、 2部3正則多面体グラフはすべてハミルトングラフであるというバーネットの予想は未解決である。^[10]

ハミルトン閉路を持たないすべての極大平面グラフには、マイナーとしてヘルシェルグラフがあります。ヘルシェルグラフは、3つのマイナー極小非ハミルトン3頂点連結グラフの1つであると予想されています。他の2つは、完全な二部グラフと、ヘルシェルグラフとを3頂点セパレータで2つの対称的な半分に分割し、各グラフの半分を組み合わせて形成されるグラフです。 ^[11] $K_{3,4}$ $K_{3,4}$

ハーシェルグラフは、中間グラフが2つの辺が互いに素なハミルトン閉路にハミルトン分解されない多面体グラフの例でもある。ハーシェルグラフの中間グラフは、ハーシェルグラフの各辺に1つずつ、計18の頂点を持つ4正則グラフである。中間グラフでは、対応するハーシェルグラフの辺がいずれかの面で連続している場合、2つの頂点が隣接している。^[12]これは4頂点連結で、本質的には 6辺連結である。ここで、グラフが-頂点連結または-辺連結であるとは、それぞれ -頂点または -辺より少ない数を削除してもグラフが切断されない場合である。平面グラフは、常に次数が最大5の頂点を持ち、隣接する辺を削除するとグラフが切断されるため、6辺連結にはならない。「本質的に6辺で接続されている」という用語は、グラフを切断するこの単純な方法が無視され、5つ以下の辺を削除することで、それぞれが少なくとも2つの頂点を持つ2つのサブグラフにグラフを切断することは不可能であることを意味します。^[13] $k$ $k$ $k$

歴史

ハーシェルグラフは、ウィリアム・ローワン・ハミルトンのイコシアンゲームに関する初期の論文を書いたイギリスの天文学者、アレクサンダー・スチュワート・ハーシェルにちなんで名付けられました。これは、多面体、通常は正十二面体上のハミルトン閉路を見つけるパズルです。ハーシェルグラフは、解のないゲームを与えるために十二面体の代わりに使用できる最小の凸多面体を記述します。ハーシェルの論文では、正四面体と正二十面体のグラフ上のイコシアンゲームの解についてのみ説明されており、ハーシェルグラフについては説明されていませんでした。^[14] 「ハーシェルグラフ」という名前は、 1976年に出版されたジョン・エイドリアン・ボンディとUSRマーティによるグラフ理論の教科書に早くから登場しています。 ^[15]グラフ自体は、たとえばHSMコクセターによって以前に説明されていました。^[4]

参考文献

^ abcde Lawson-Perfect, Christian (2013年10月13日)、「An enneahedron for Herschel」、The Aperiodical 、 2016年12月7日閲覧。
^ Holton, DA (1983)、「Cycles in graphs」、Casse, LRA (ed.)、Combinatorial Mathematics X: Proceedings of the Conference Held in Adelaide, Australia, August 23-27, 1982、Lecture Notes in Mathematics、vol. 1036、ベルリン: Springer、pp. 24–48、doi :10.1007/BFb0071507、ISBN 978-3-540-12708-6、MR 0731570
^ Grünbaum、Branko (2003)、「13.1 Steinitz の定理」、凸多面体、Graduate Texts in Mathematics、vol. 221 (第 2 版)、シュプリンガー版、235 ～ 244 ページ、ISBN 0-387-40409-0
^ ab Coxeter, HSM (1948)、Regular Polytopes、ロンドン：メシューエン、p. 8
^ コンスタンティニデス、アンソニー F.; コンスタンティニデス、ジョージ A. (2018 年 10 月)、「スピンダウン多面体」、The Mathematical Gazette、102 (555): 447–453、doi :10.1017/mag.2018.111、S2CID 233357977
^ ab バーネット、デイビッド; ジュコビッチ、アーネスト (1970)、「3次元多面体上のハミルトン回路」、組合せ理論ジャーナル、9 (1): 54–59、doi : 10.1016/S0021-9800(70)80054-0。
^ Goldner, A.; Harary, F. (1975)、「最小の非ハミルトン最大平面グラフに関する注記」、Bull. Malaysian Math. Soc.、6 (1): 41–42; 同誌6 (2):33(1975)および8 :104-106(1977)も参照。Hararyの出版物のリストからの引用。
^ テイト、PG（1884）、「リストのトポロジー」、哲学雑誌、第5シリーズ、17：30–46; 段落(16)、41-42ページを参照。Scientific Papers、第2巻、85-98ページに再掲載
^ Tutte, WT (1946)、「ハミルトン回路について」、ロンドン数学会誌、21 (2): 98–101、doi :10.1112/jlms/s1-21.2.98
^ Šámal, Robert (2007 年 6 月 11 日)、Barnette の予想、Open Problem Garden 、2011 年2 月 24 日閲覧
^ ディン、グオリ、マーシャル、エミリー（2018）、「最小連結非ハミルトングラフ」、グラフと組合せ論、34（2）：289–312、doi：10.1007/s00373-018-1874-z、MR 3774453、S2CID 253891751 $k$
^ ボンディ、JA ; Häggkvist, R. (1981)、「4 正則平面グラフにおけるエッジ分離ハミルトンサイクル」、Aequationes Mathematicae、22 (1): 42–45、doi :10.1007/BF02190157、S2CID 120729891。
^ キラーリ、チャバ; Péterfalvi、Ferenc (2012)、「長いパスのない平衡型汎用回路」、離散数学、312 (15): 2262–2271、doi : 10.1016/j.disc.2012.03.031、MR 2926099
^ ハーシェル、AS（1862）、「サー・ウィリアム・ハミルトンのイコシアンゲーム」、純粋および応用数学季刊誌、5：305
^ Bondy, JA ; Murty, USR (1976)、「グラフ理論とその応用」、ノースホランド、p. 53、MR 0411988

外部リンク

ワイスタイン、エリック W.、「ハーシェルグラフ」、MathWorld

[clp-1] Lawson-Perfect, Christian (2013年10月13日)、「An enneahedron for Herschel」、The Aperiodical 、 2016年12月7日閲覧。

[holton-2] Holton, DA (1983)、「Cycles in graphs」、Casse, LRA (ed.)、Combinatorial Mathematics X: Proceedings of the Conference Held in Adelaide, Australia, August 23-27, 1982、Lecture Notes in Mathematics、vol. 1036、ベルリン: Springer、pp. 24–48、doi :10.1007/BFb0071507、ISBN 978-3-540-12708-6、MR 0731570

[grunbaum-3] Grünbaum、Branko (2003)、「13.1 Steinitz の定理」、凸多面体、Graduate Texts in Mathematics、vol. 221 (第 2 版)、シュプリンガー版、235 ～ 244 ページ、ISBN 0-387-40409-0

[coxeter-4] Coxeter, HSM (1948)、Regular Polytopes、ロンドン：メシューエン、p. 8

[concon-5] コンスタンティニデス、アンソニー F.; コンスタンティニデス、ジョージ A. (2018 年 10 月)、「スピンダウン多面体」、The Mathematical Gazette、102 (555): 447–453、doi :10.1017/mag.2018.111、S2CID 233357977

[barjuc-6] バーネット、デイビッド; ジュコビッチ、アーネスト (1970)、「3次元多面体上のハミルトン回路」、組合せ理論ジャーナル、9 (1): 54–59、doi : 10.1016/S0021-9800(70)80054-0。

[golhar-7] Goldner, A.; Harary, F. (1975)、「最小の非ハミルトン最大平面グラフに関する注記」、Bull. Malaysian Math. Soc.、6 (1): 41–42; 同誌6 (2):33(1975)および8 :104-106(1977)も参照。Hararyの出版物のリストからの引用。

[tait-8] テイト、PG（1884）、「リストのトポロジー」、哲学雑誌、第5シリーズ、17：30–46; 段落(16)、41-42ページを参照。Scientific Papers、第2巻、85-98ページに再掲載

[tutte-9] Tutte, WT (1946)、「ハミルトン回路について」、ロンドン数学会誌、21 (2): 98–101、doi :10.1112/jlms/s1-21.2.98

[garden-10] Šámal, Robert (2007 年 6 月 11 日)、Barnette の予想、Open Problem Garden 、2011 年2 月 24 日閲覧

[dinmar-11] ディン、グオリ、マーシャル、エミリー（2018）、「最小連結非ハミルトングラフ」、グラフと組合せ論、34（2）：289–312、doi：10.1007/s00373-018-1874-z、MR 3774453、S2CID 253891751 $k$

[bonhag-12] ボンディ、JA ; Häggkvist, R. (1981)、「4 正則平面グラフにおけるエッジ分離ハミルトンサイクル」、Aequationes Mathematicae、22 (1): 42–45、doi :10.1007/BF02190157、S2CID 120729891。

[kirpet-13] キラーリ、チャバ; Péterfalvi、Ferenc (2012)、「長いパスのない平衡型汎用回路」、離散数学、312 (15): 2262–2271、doi : 10.1016/j.disc.2012.03.031、MR 2926099

[herschel-14] ハーシェル、AS（1862）、「サー・ウィリアム・ハミルトンのイコシアンゲーム」、純粋および応用数学季刊誌、5：305

[bonmur-15] Bondy, JA ; Murty, USR (1976)、「グラフ理論とその応用」、ノースホランド、p. 53、MR 0411988