ヒーウッドグラフ
数学のグラフ理論の分野におけるヒーウッドグラフ（英: Heawood graph）は、パーシー・ジョン・ヒーウッドの名にちなむ、14の頂点と21の辺を含むある無向グラフである[1]。
| ヒーウッドグラフ | |
|---|---|
 | |
| 命名者 | パーシー・ジョン・ヒーウッド |
| 頂点 | 14 |
| 辺 | 21 |
| 半径 | 3 |
| 直径 | 3 |
| 内周 | 6 |
| 自己同型 | 336 (PGL2(7)) |
| 彩色数 | 2 |
| 彩色指数 | 3 |
| 特性 |
2部 立方体 ケージ 距離推移的 距離正則 トロイダル ハミルトン 対称 向き付け可能・単純 |
組合せの性質
編集ヒーウッドグラフは立方体であり、それに含まれるすべての閉路には六つ以上の辺がある。これよりも小さいすべての立方体グラフにはより短い閉路しか含まれないため、ヒーウッドグラフは 6-ケージの、内周 6 の最小の立方体グラフである。また、距離推移グラフ（フォスター調査を参照）でもあり、したがって距離正則である[2]。
ヒーウッドグラフには 24 の完全マッチングが存在する;各マッチングに対し、それに含まれない辺の集合はハミルトン閉路を形成する。例えば、ページ右上の図は、マッチングを形成する閉路からなる内部対角（internal diagonal）を備える閉路上の頂点を示しているグラフである。その閉路を二つのマッチングに分けることで、ヒーウッドグラフを三つの完全マッチング（すなわち、3辺彩色）に分ける方法が八通りある[2]。どの二つの完全マッチングと、どの二つのハミルトン閉路も、グラフの対称性によってお互い交換することが出来る[3]。
ヒーウッドグラフには 6-頂点の閉路が 28 含まれる。そのような 6-閉路は、必ず三つの他の 6-閉路と互いに素になっている;そのような三つの 6-閉路において、どの一つも必ず他の二つの対称差（symmetric difference）になっている。6-閉路に対して一つの頂点と、6-閉路の互いに素な各ペアに対して一つの辺を備えるグラフは、コクセターグラフである[4]。
幾何および位相的性質
編集ヒーウッドグラフはトロイダルグラフである; すなわち、ヒーウッドグラフはトーラス上で交叉することなく埋め込まれる。このタイプの一つの埋め込みは、その頂点と辺を三次元ユークリッド空間へ、あるトーラスの位相を備える非凸多面体（シラッシの環状多面体）の頂点と辺の集合として配置する。
グラフの名の由来であるパーシー・ジョン・ヒーウッドは1890年、トーラスの多角形への全ての細分割において、その多角形領域は高々七色の色で彩色されることを証明した[5][6]。ヒーウッドグラフは、境界が tight であるような、七つの互いに近接した領域を備えるトーラスの細分割を形成する。
ヒーウッドグラフはまたファノ平面のレヴィグラフでもあり、幾何における点と距離の間の incidences を表すグラフである。この解釈によると、ヒーウッドグラフに含まれる 6-閉路は、ファノ平面における三角形に対応する。
ヒーウッドグラフの交叉数は 3 であり、そのような交叉数を持つ立方体グラフの中では最小である。ヒーウッドグラフを含む、交叉数 3 で位数 14 のグラフは 8 つある。
ヒーウッドグラフは単位距離グラフである: 隣接する頂点はちょうど距離が 1 だけ離れており、同じ点に埋め込まれている頂点はなく、また、辺に含まれるある点に埋め込まれる頂点もないような平面に、そのグラフは埋め込まれる。しかしながら、そのグラフに備わっている対称性は、このタイプの知られている埋め込みにおいては欠落している[7]。
代数的性質
編集ヒーウッドグラフの自己同型群は、位数 336 の射影線型群 PGL2(7) と同型である[8]。それは、グラフの頂点、辺および弧の上で推移的に作用する。したがって、ヒーウッドグラフは対称グラフである。任意の頂点や辺を、任意の別の頂点や辺へと写す自己同型が存在する。フォスター調査によれば、F014A と番号付けられるヒーウッドグラフは、頂点が14個であるような唯一つの立方体対称グラフである[9][10]。
ヒーウッドグラフの固有多項式は である。ヒーウッドグラフはこの固有多項式を持つ唯一つのグラフであり、これによってヒーウッドグラフはそのスペクトルによって決定付けられるグラフとなっている。
ギャラリー
編集
参考文献
編集- ^ Weisstein, Eric W. "Heawood Graph". mathworld.wolfram.com (英語).
- ^ a b Brouwer, Andries E.. “Heawood graph”. Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989). 2012年10月19日閲覧。
- ^ Abreu, M.; Aldred, R. E. L.; 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, MR2099150.
- ^ Dejter, Italo J. (2011), “From the Coxeter graph to the Klein graph”, Journal of Graph Theory, arXiv:1002.1960, doi:10.1002/jgt.20597.
- ^ Brown, Ezra (2002). “The many names of (7,3,1)”. Mathematics Magazine 75 (2): 83–94. doi:10.2307/3219140. JSTOR 3219140.
- ^ Heawood, P. J. (1890). “Map colouring theorems”. Quarterly J. Math. Oxford Ser. 24: 322–339.
- ^ Gerbracht, Eberhard H.-A. (2009). Eleven unit distance embeddings of the Heawood graph. arXiv:0912.5395.
- ^ Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. New York: North Holland. p. 237. ISBN 0-444-19451-7. オリジナルの2010年4月13日時点におけるアーカイブ。
- ^ Royle, G. "Cubic Symmetric Graphs (The Foster Census)."
- ^ Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.