ヒーウッドグラフ

ヒーウッドグラフ
ヒーウッドグラフ
にちなんで名付けられました	パーシー・ジョン・ヒーウッド
頂点	14
エッジ	21
半径	3
直径	3
周囲	6
自己同型写像	336 ( PGL 2 (7) )
彩色数	2
色度指数	3
属	1
本の厚さ	3
順番待ち番号	2
不動産	二部グラフ立方体ケージ距離推移的距離正則トーラスハミルトニアン対称的方向付け可能単純
	グラフとパラメータの表

グラフ理論の数学分野において、ヒーウッドグラフは、パーシー・ジョン・ヒーウッドにちなんで名付けられた、14個の頂点と21個の辺を持つ無向グラフである。^[¹^]

組み合わせ特性

このグラフは立方体であり、グラフ内のすべてのサイクルは6つ以上の辺を持つ。より小さい立方体グラフはすべてサイクルが短いため、このグラフは6ケージ、つまり周長6の最小の立方体グラフである。これは距離推移グラフ（フォスター国勢調査を参照）であり、したがって距離正則である。^{[ 2 ]}

ヒーウッドグラフには 24 個の完全マッチングがあります。各マッチングについて、マッチングに含まれないエッジの集合はハミルトン閉路を形成します。たとえば、図はグラフの頂点が閉路上に配置され、閉路の内部対角線がマッチングを形成している様子を示しています。閉路のエッジを 2 つのマッチングに分割することで、ヒーウッドグラフを 3 つの完全マッチング (つまり、エッジを 3 色に塗り分けること) に 8 通りの異なる方法で分割できます。^{[ 2 ]}グラフの対称性により、任意の 2 つの完全マッチングと任意の 2 つのハミルトン閉路は相互に変換できます。^{[ 3 ]}

ヒーウッドグラフには28個の6頂点サイクルがあります。各6サイクルは、他の3つの6サイクルと互いに素です。これらの3つの6サイクルは、それぞれ他の2つの対称差です。6サイクルごとに1つのノードがあり、互いに素な6サイクルのペアごとに1つのエッジがあるグラフは、コクセターグラフです。^{[ 4 ]}

幾何学的特性および位相的特性

ヒーウッドグラフはトーラスグラフです。つまり、交差なしにトーラス上に埋め込むことができます。その結果、7 つの六角形の面を持つ正則マップ ${6,3}$ $2,1が得られます。$ ^[⁵^]マップの各面は他のすべての面に隣接しているため、結果としてマップを彩色するには 7 色が必要です。マップとグラフは1890 年にパーシー・ジョン・ヒーウッドによって発見され、彼はトーラス上のマップは 7 色を超える色を必要としないことを証明し、したがってこのマップは極大であることを証明しました。^[⁶^]^[⁷^]

この地図は、シラッシ多面体^{[ 8 ]}として忠実に実現できる。これは、四面体以外で、すべての面のペアが隣接している唯一の既知の多面体である。

ファノ平面とそのレヴィグラフの2つの表現（以下、二部グラフとして示す）

ヒーウッドグラフはファノ平面のレヴィグラフであり、^[⁵^]_{その幾何学における点と線の間の関係を表すグラフである}。この解釈によれば、ヒーウッドグラフの6サイクルはファノ平面の三角形に対応する。また、ヒーウッドグラフは群SL3 (F2 ₎のティッツビルディングである。

ヒーウッドグラフは交差数が3であり、その交差数を持つ最小の3次グラフである（OEISのシーケンスA110507）。ヒーウッドグラフを含め、交差数が3の次数14のグラフは8種類存在する。

ヒーウッドグラフは、コリン・ド・ヴェルディエールグラフ不変量 $μ = 6$ を持つ最小の3次グラフである。^{[ 9 ]}

ヒーウッドグラフは単位距離グラフです。隣接する頂点間の距離がちょうど1になるように平面に埋め込むことができ、2つの頂点が同じ点に埋め込まれることはなく、また、辺内の点に埋め込まれる頂点もありません。^{[ 10 ]}

代数的性質

ヒーウッドグラフの自己同型群は、位数 336 の射影線形群 PGL 2 (7) と同型です。[ 11 ]グラフ_の^頂点、辺、弧に推移的に作用します。したがって、ヒーウッドグラフは対称グラフです。任意の頂点を他の任意の頂点に、任意の辺を他の任意の辺に写像する自己同型があります。さらに強く言うと、ヒーウッドグラフは4-弧推移的です。^{[ 12 ]}フォスターセンサスによると、F014A として参照されるヒーウッドグラフは、14 個の頂点を持つ唯一の 3 次対称グラフです。^{[ 13 ]}^{[ 14 ]}

本の厚さは3 、キュー番号は2です。^{[ 15 ]}

ヒーウッドグラフの特性多項式は $(x-3)(x+3)(x^{2}-2)^{6}$ これは、この特性多項式を持つ唯一のグラフであり、スペクトルによって決定されるグラフである。

ギャラリー

交差番号3と1-平面
色度指数3
色彩番号2
トーラス（正方形として表示）に埋め込まれている
トーラスに埋め込まれている（動画を参照）
シラッシ多面体

参考文献

↑ Weisstein, Eric W. "Heawood Graph" . MathWorld .
1 2 Brouwer, Andries E. 「Heawood graph」。書籍『距離正則グラフ』（Brouwer、Cohen、Neumaier著、Springer、1989年）への加筆および訂正
↑ Abreu, M.; Aldred, REL; Funk, M.; Jackson, Bill; Labbate, D.; Sheehan, J. (2004), "Graphs and digraphs with all 2-factors isomorphic", Journal of Combinatorial Theory, Series B , 92 (2): 395– 404, doi : 10.1016/j.jctb.2004.09.004 , MR 2099150 。
↑ Dejter、Italo J. (2011)、「Coxeter グラフからクライングラフへ」、Journal of Graph Theory、70 : 1–9、arXiv : 1002.1960、doi : 10.1002/jgt.20597、S2CID 754481 。
1 2 Coxeter (1950)、「自己双対構成と正則グラフ」(PDF)、Bulletin of the American Mathematical Society、56 (5): 413–455、doi : 10.1090/S0002-9904-1950-09407-5
↑ Brown, Ezra (2002). "The many names of (7,3,1)" (PDF) . Mathematics Magazine . 75 (2): 83– 94. doi : 10.2307/3219140 . JSTOR 3219140 . 2012-02-05 のオリジナル(PDF)からアーカイブ済み。2006-10-27に取得。
↑ Heawood, PJ (1890). "地図色定理". Quarterly Journal of Mathematics . First Series. 24 : 322– 339.
↑ Szilassi、Lajos (1986)、「通常のトロイド」(PDF)、構造トポロジー、13 : 69–80
↑ Hein van der Holst (2006). "Graphs and obstructions in four dimensions" (PDF) . Journal of Combinatorial Theory, Series B . 96 (3): 388– 404. doi : 10.1016/j.jctb.2005.09.004 .
↑ Gerbracht, Eberhard H.-A. (2009), Eleven unit distance embeddings of the Heawood graph , arXiv : 0912.5395 , Bibcode : 2009arXiv0912.5395G。
↑ Bondy, JA ; Murty, USR (1976). Graph Theory with Applications . New York: North Holland. p . 237. ISBN 0-444-19451-72010年4月13日にオリジナルからアーカイブされました。 2019年12月18日に取得。
↑ Conder, Marston; Morton, Margaret (1995). "Classification of Trivalent Symmetric Graphs of Small Order" (PDF) . Australasian Journal of Combinatorics . 11 : 146.
↑ Royle, G.「立方対称グラフ（フォスター国勢調査）」Wayback Machineに2008年7月20日にアーカイブ済み
↑ Conder, M.および Dobcsányi, P.「768 頂点までの三価対称グラフ」J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
↑ジェシカ・ウォルツ、「 SATを用いた線形レイアウトの設計」。修士論文、テュービンゲン大学、2018年

[1] Weisstein, Eric W. "Heawood Graph" . MathWorld .

[brouwer-2] 1 2 Brouwer, Andries E. 「Heawood graph」。書籍『距離正則グラフ』（Brouwer、Cohen、Neumaier著、Springer、1989年）への加筆および訂正

[3] Abreu, M.; Aldred, REL; Funk, M.; Jackson, Bill; Labbate, D.; Sheehan, J. (2004), "Graphs and digraphs with all 2-factors isomorphic", Journal of Combinatorial Theory, Series B , 92 (2): 395– 404, doi : 10.1016/j.jctb.2004.09.004 , MR 2099150 。

[4] Dejter、Italo J. (2011)、「Coxeter グラフからクライングラフへ」、Journal of Graph Theory、70 : 1–9、arXiv : 1002.1960、doi : 10.1002/jgt.20597、S2CID 754481 。

[Coxeter-5] 1 2 Coxeter (1950)、「自己双対構成と正則グラフ」(PDF)、Bulletin of the American Mathematical Society、56 (5): 413–455、doi : 10.1090/S0002-9904-1950-09407-5

[6] Brown, Ezra (2002). "The many names of (7,3,1)" (PDF) . Mathematics Magazine . 75 (2): 83– 94. doi : 10.2307/3219140 . JSTOR 3219140 . 2012-02-05 のオリジナル(PDF)からアーカイブ済み。2006-10-27に取得。

[7] Heawood, PJ (1890). "地図色定理". Quarterly Journal of Mathematics . First Series. 24 : 322– 339.

[8] Szilassi、Lajos (1986)、「通常のトロイド」(PDF)、構造トポロジー、13 : 69–80

[9] Hein van der Holst (2006). "Graphs and obstructions in four dimensions" (PDF) . Journal of Combinatorial Theory, Series B . 96 (3): 388– 404. doi : 10.1016/j.jctb.2005.09.004 .

[10] Gerbracht, Eberhard H.-A. (2009), Eleven unit distance embeddings of the Heawood graph , arXiv : 0912.5395 , Bibcode : 2009arXiv0912.5395G。

[11] Bondy, JA ; Murty, USR (1976). Graph Theory with Applications . New York: North Holland. p . 237. ISBN 0-444-19451-72010年4月13日にオリジナルからアーカイブされました。 2019年12月18日に取得。

[12] Conder, Marston; Morton, Margaret (1995). "Classification of Trivalent Symmetric Graphs of Small Order" (PDF) . Australasian Journal of Combinatorics . 11 : 146.

[13] Royle, G.「立方対称グラフ（フォスター国勢調査）」Wayback Machineに2008年7月20日にアーカイブ済み

[14] Conder, M.および Dobcsányi, P.「768 頂点までの三価対称グラフ」J. Combin. Math. Combin. Comput. 40, 41-63, 2002.

[15] ジェシカ・ウォルツ、「 SATを用いた線形レイアウトの設計」。修士論文、テュービンゲン大学、2018年

[

[ 2 ]

[ 3 ]

[ 4 ]

[

[

[

[ 8 ]

[ 9 ]

[ 10 ]

頂点、辺

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]