リュブリャナグラフ
| リュブリャナグラフ | |
|---|---|
 | |
| 頂点 | 112 |
| エッジ | 168 |
| 半径 | 7 |
| 直径 | 8 |
| 胴回り | 10 |
| 自己同型 | 168 |
| 彩色数 | 2 |
| 色指数 | 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] 2 .
リュブリャナグラフは、56本の直線と56本の点を持つ四角形のない構成であるリュブリャナ構成のレヴィグラフです。 [ 1 ]この構成では、各直線にはちょうど3つの点が含まれ、各点はちょうど3本の直線に属し、2本の直線は最大でも1つの点で交差します。
代数的性質
リュブリャナグラフの自己同型群は位数168の群である。この群はグラフの辺には推移的に作用するが、頂点には作用しない。つまり、すべての辺を他の任意の辺に繋ぐ対称性は存在するが、すべての頂点を他の任意の頂点に繋ぐ対称性は存在しない。したがって、リュブリャナグラフは半対称グラフであり、 54頂点のグレイグラフと110頂点のイオフィノヴァ・イワノフグラフに次いで3番目に小さい立方半対称グラフである。[ 3 ]
リュブリャナグラフの特性多項式は
歴史
リュブリャナグラフは、1993年にBrouwer、Dejter、Thomassen [ 4 ]によって、 Dejterグラフ の自己相補サブグラフとして初めて発表されました。[ 5 ]
1972年に、バウワーは既にRMフォスターによって発見された、未発表ではあるが頂点が推移的ではない112頂点の辺を持つ立方グラフについて話していた。 [ 6 ]コンダー、マルニチ、マルシチ、ピサンスキ、ポトチニクは2002年にこの112頂点のグラフを再発見し、スロベニアの首都にちなんでリュブリャナグラフと名付けた。[ 1 ]彼らは、これが唯一の112頂点の辺を持つ立方グラフだが頂点が推移的ではないことを証明し、したがってそれがフォスターによって発見されたグラフであった。
ギャラリー
リュブリャナグラフはハミルトングラフであり、二部グラフである。- リュブリャナグラフの色指数は 3です。
- リュブリャナ グラフの別の図。
- リュブリャナ グラフは、この構成のレヴィ グラフです。
参考文献
- ^ a b c dコンドル、M. ;マルニッチ、A.マルシッチ、D.ピサンスキー、T.とポトチニク、P.「リュブリャナグラフ」。 2002 年[1]。
- ^ Weisstein, Eric W. 「リュブリャナグラフ」 . MathWorld .
- ^マーストン・コンドル、アレクサンダー・マルニッチ、ドラガン・マルシッチ、プリモシュ・ポトチニク。 「最大 768 頂点の半対称立方体グラフの調査。」 Journal of Algebraic Combinatorics: 国際ジャーナル。第 23 巻、第 3 号、255 ～ 294 ページ、2006 年。
- ^ Brouwer, AE; Dejter, IJ; Thomassen, C. 「超立方体の高度に対称な部分グラフ」 J. Algebraic Combinat. 2, 25-29, 1993.
- ^ Klin M.; Lauri J.; Ziv-Av M.「112頂点上の2つの半対称グラフ間のリンク：アソシエーションスキームのレンズを通して」、Jour. Symbolic Comput.、47–10、2012年、1175–1191。
- ^ Bouwer, IA「頂点ではなく辺の推移的正則グラフについて」J. Combin. Th. Ser. B 12, 32-40, 1972.