リュブリャナグラフ

リュブリャナグラフ
ヒーウッドグラフの被覆グラフとしてのリュブリャナグラフ
頂点	112
エッジ	168
半径	7
直径	8
胴回り	10
自己同型	168
彩度数	2
色指数	3
プロパティ	3次半 対称 ハミルトニアン
グラフとパラメータの表

数学のグラフ理論の分野において、リュブリャナグラフは112の頂点と168の辺を持つ無向 二部グラフであり、2002年に再発見され、リュブリャナ（スロベニアの首都）にちなんで名付けられました。^{[1] [2]}

これは直径8、半径7、彩色数2、彩色指数3の立方体グラフです。その内周は10で、長さ10の周期がちょうど168個あります。長さ12の周期も168個あります。^[1]

リュブリャナグラフはハミルトングラフであり、 LCF表記法から構築できます : [47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15, -49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, -31, -39] ² .

リュブリャナグラフは、56本の直線と56本の点を持つ四角形のない構成であるリュブリャナ構成のレヴィグラフです。 ^[1]この構成では、各直線には正確に3つの点が含まれ、各点は正確に3本の直線に属し、2本の直線は最大でも1つの点で交差します。

リュブリャナグラフの自己同型群は位数168の群である。これはグラフの辺には推移的に作用するが、頂点には作用しない。つまり、すべての辺を他の任意の辺に結ぶ対称性はあるが、すべての頂点を他の任意の頂点に結ぶ対称性はない。したがって、リュブリャナグラフは半対称グラフであり、 54頂点のグレイグラフと110頂点のイオフィノバ・イワノフグラフに次いで3番目に小さい立方半対称グラフである。^[3]

リュブリャナグラフの特性多項式は

${\displaystyle (x-3)x^{14}(x+3)(x^{2}-x-4)^{7}(x^{2}-2)^{6}(x^{2}+x-4)^{7}(x^{4}-6x^{2}+4)^{14}.\ }$

リュブリャナグラフは、1993年にBrouwer、Dejter、Thomassen ^{[4]によって}、Dejterグラフ^[5] の自己相補的サブグラフとして初めて発表されました。

1972年に、バウワーはRMフォスターによって発見された、未発表ではあるが辺は推移的だが頂点は推移的ではない112頂点立方グラフについてすでに話していた。^[6] コンダー、マルニッチ、マルシッチ、ピサンスキ、ポトチニクは2002年にこの112頂点グラフを再発見し、スロベニアの首都にちなんでリュブリャナグラフと名付けた。^[1]彼らは、これが唯一の112頂点の辺は推移的だが頂点は推移的ではない立方グラフであることを証明し、したがってそれがフォスターによって発見されたグラフであった。

• 
  リュブリャナグラフはハミルトングラフであり、二部グラフである。
• 
  リュブリャナグラフの色指数は 3です。
• 
  リュブリャナ グラフの別の図。
• 
  リュブリャナ グラフは、この構成のレヴィ グラフです。