クライングラフ

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

3次クライングラフ

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

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

フォスター国勢調査によると、F056Bと呼ばれるクライングラフは、2部ではない56頂点の唯一の立方対称グラフです。^[2]

この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 です。

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

これは交差配列を持つ唯一の距離正則グラフであるが、距離推移グラフではない。^[5] $\{7,4,1;1,2,7\}$

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

この24頂点クライングラフの特性多項式はに等しい。^[6] $(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、イタロ J. (2012)。「コクセターグラフからクライングラフへ」。グラフ理論ジャーナル。70 (1): 1-9。arXiv : 1002.1960。土井：10.1002/jgt.20597。MR 2916063。
^ Schulte, Egon; Wills, JM (1985). 「種数3のリーマン面上のフェリックス・クラインの写像{3, 7}8の多面体実現」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 .