クライングラフ

グラフ理論の数学分野において、クライングラフは、それぞれ84本の辺を持つ、異なるが関連性のある2つの正則グラフである。これらはそれぞれ種数3の向き付け可能な曲面に埋め込むことができ、その曲面内で双対グラフを形成する。

3次クライングラフ

これは、フェリックス・クラインにちなんで名付けられた、56個の頂点と84個の辺を持つ3正則（立方体）グラフです。

これはハミルトングラフであり、彩色数3、彩色指数3、半径6、直径6、周長7です。また、3頂点連結グラフであり、3辺連結グラフでもあります。本の厚さは3、待ち行列の数は2です。 ^{[ 1 ]}

これは、種数-3の向き付け可能な曲面（クライン四次曲面として表現できる）に埋め込むことができ、そこで24個の七角形の面を持つクライン写像、シュレーフリ記号{7,3} ₈を形成する。

フォスターの調査によると、F056B と参照されるクライングラフは、56 頂点の立方対称グラフの中で、二部グラフではない唯一のグラフである。^{[ 2 ]}

これは28頂点のコクセターグラフから導き出すことができる。^{[ 3 ]}

この56頂点のクライングラフの特性多項式は、 $x^{7}\,(x-3)\,(x+2)^{6}\left(x^{2}-2\right)^{6}\left(x^{2}+x-4\right)^{7}\left(x^{2}-2x-1\right)^{8}$

これは、フェリックス・クラインにちなんで名付けられた、24個の頂点と84個の辺を持つ7正則グラフです。

これはハミルトン関数であり、彩色数は4、彩色指数は7、半径は3、直径は3、周囲は3である。

これは、56 個の三角形面を持つクライン写像の双対を形成する、種数 3 の向き付け可能な曲面に埋め込むことができ、シュレーフリ記号は{3,7} ₈です。^{[ 4 ]}

これは交差配列を持つユニークな距離正則グラフです $\{7,4,1;1,2,7\}$ ;しかし、これは距離推移グラフではない。^{[ 5 ]}

7価クライングラフの自己同型群は、3次クライン写像と同じ位数336の群であり、同様にその半辺に推移的に作用する。

この24頂点のクライングラフの特性多項式は、 $(x-7)(x+1)^{7}(x^{2}-7)^{8}$ [ ⁶^]

↑ Wolz, Jessica; SATを用いた線形レイアウトの設計。修士論文、テュービンゲン大学、2018年
↑ Conder, M. ; Dobcsányi, P. (2002). "768頂点までの三価対称グラフ". J. Combin. Math. Combin. Comput . 40 : 41– 63.。
↑ Dejter、Italo J. (2012)。「コクセターグラフからクライングラフへ」。グラフ理論ジャーナル。70 (1): 1–9 . arXiv : 1002.1960。土井：10.1002/jgt.20597。MR 2916063。
↑ Schulte, Egon; Wills, JM (1985). "A Polyhedral Realization of Felix Klein's Map {3, 7} ₈ on a Riemann Surface of Genus 3" . J. London Math. Soc . s2-32 (3): 539– 547. doi : 10.1112/jlms/s2-32.3.539 .
↑ブラウワー、アンドリース;コーエン、アルジェ。ノイマイヤー、アーノルド (1989)。距離-正規グラフ。スプリンガー・フェルラーグ。 p. 386 . ISBN 978-0-387-50619-7。
↑ van Dam, ER; Haemers, WH; Koolen, JH; Spence, E. (2006). "スペクトルによるグラフの距離正則性の特性評価" . J. Combin. Theory Ser. A . 113 (8): 1805– 1820. doi : 10.1016/j.jcta.2006.03.008 .