| ブリンクマングラフ | |
|---|---|
 ブリンクマングラフ | |
| 名前の由来 | グンナー・ブリンクマン |
| 頂点 | 21 |
| エッジ | 42 |
| 半径 | 3 |
| 直径 | 3 |
| 胴回り | 5 |
| 自己同型 | 14 ( D 7 ) |
| 彩色数 | 4 |
| 色指数 | 5 |
| 本の厚さ | 3 |
| キュー番号 | 2 |
| プロパティ | オイラー ハミルトニアン |
| グラフとパラメータの表 | |
数学のグラフ理論の分野において、ブリンクマングラフは、1992年にグンナー・ブリンクマンによって発見された21の頂点と42の辺を持つ4正則グラフです。[1]ブリンクマンとメリンガーによって1997年に初めて発表されました。[2]
彩色数4、彩色指数5、半径3、直径3、内周5である。また、3頂点連結グラフであり、3辺連結グラフでもある。彩色数4、内周5の4正則グラフの中で最小のグラフである。[2]本の厚みは3、列数は2である。 [3]
ブルックスの定理によれば、奇数サイクルとクリークを除くすべてのk正則グラフの彩色数は最大でkである。また、1959年以来、すべてのkとlに対して、内周が lであるk彩色グラフが存在することが知られていた。[4]これら2つの結果と、 Chvátalグラフを含むいくつかの例に関連して、ブランコ・グリュンバウムは1970年に、すべてのkとlに対して、内周が lであるk彩色k正則グラフが存在すると予想した。[5] Chvátalグラフはこの予想のk = l = 4の場合を解き 、Brinkmannグラフはk = 4、l = 5の場合を解きます。Grünbaumの予想は、十分に大きなk に対してJohannsenによって反証されました。彼は、三角形のないグラフの彩色数はO(Δ/log Δ)であることを示しました。ここで、Δは最大頂点次数であり、Oは大きなO表記を導入します。[6]しかし、この反証にもかかわらず、例を見つけることは興味深いままであり、非常に少数しか知られていません。
ブリンクマングラフの彩色多項式はx 21 − 42 x 20 + 861 x 19 − 11480 x 18 + 111881 x 17 − 848708 x 16 + 5207711 x 15 − 26500254 x 14 + 113675219 x 13 − 415278052 x 12 + 1299042255 x 11 − 3483798283 x 10 + 7987607279 x 9 − 15547364853 x 8 + 25384350310 x 7 − 34133692383 x 6 + 36783818141 x 5 − 30480167403 x 4 + 18168142566 x 3 − 6896700738 x 2 + 1242405972 x （ OEISの配列A159192）。
代数的性質
ブリンクマン グラフは頂点推移グラフではなく、その完全な自己同型群は、回転と反射の両方を含む 七角形の対称性の群である、順序 14 の二面体群と同型です。
ブリンクマングラフの特性多項式は です。
ギャラリー
参考文献
- ^ Brinkmann, G.「同型性チェックよりも高速な立方グラフ生成」プレプリント92-047 SFB 343.ドイツ、ビーレフェルト：ビーレフェルト大学、1992年。
- ^ ab Brinkmann, G. および Meringer, M. 「内周5の最小の4-正則4-彩色グラフ」Graph Theory Notes of New York 32, 40-41, 1997.
- ^ ジェシカ・ウォルツ、「SATを用いた線形レイアウトのエンジニアリング」。修士論文、テュービンゲン大学、2018年
- ^ エルデシュ、ポール（1959）「グラフ理論と確率」、カナダ数学ジャーナル、11：34-38、doi：10.4153/CJM-1959-003-9。
- ^ Grünbaum, B. (1970)、「グラフ彩色における問題」、アメリカ数学月刊誌、77 (10)、アメリカ数学会: 1088– 1092、doi :10.2307/2316101、JSTOR 2316101。
- ^ リード、BA（1998）、「ω、Δ、χ」、グラフ理論ジャーナル、27（4）：177– 212、doi：10.1002 /（SICI）1097-0118（199804）27：4<177：：AID-JGT1>3.0.CO;2-K。
外部リンク
- ワイスタイン、エリック W.「ブリンクマン グラフ」。マスワールド。
