フォークマングラフのソースを表示

{{infobox graph
 | name = フォークマングラフ
 | image = [[Image:Folkman graph alt.svg|220px]]
 | image_caption = フォークマングラフ
 | namesake = ジョン・フォークマン
 | vertices = 20
 | edges = 40
 | girth = 4
 | diameter = 4
 | radius = 3
 | chromatic_number = 2
 | chromatic_index = 4
 | properties = [[ハミルトングラフ|ハミルトン]]<br>[[正則グラフ|正則]]<br>[[2部グラフ|2部]]<br>[[半対称グラフ|半対称]]<br>[[オイラーグラフ|オイラー]]<br>[[パーフェクトグラフ|パーフェクト]]
}}

[[数学]]の[[グラフ理論]]の分野における'''フォークマングラフ'''（{{Lang-en-short|Folkman graph}}）とは、{{仮リンク|ジョン・フォークマン|en|Jon Folkman}}の名にちなむ[[グラフ (離散数学)|グラフ]]であり、20個の[[頂点 (グラフ理論)|頂点]]と40個の{{仮リンク|辺 (グラフ理論)|en|Edge (graph theory)|label=辺}}を持ち、4-[[正則グラフ|正則]]な[[2部グラフ]]である<ref>{{MathWorld|title=Folkman graph|urlname=FolkmanGraph}}</ref>。

フォークマングラフは[[ハミルトングラフ|ハミルトン]]であり、[[グラフ彩色|彩色数]]は 2、[[グラフ彩色|彩色指数]]は 4、半径は 3、直径は 4、[[内周 (グラフ理論)|内周]]は 4 である。4-[[k-頂点連結グラフ|頂点連結]]かつ 4-[[k-辺連結グラフ|辺連結]]な[[パーフェクトグラフ]]でもある。

== 代数的性質 ==
フォークマングラフの[[自己同型|自己同型群]]は、その辺上では推移的に作用するが、頂点上ではそのように作用しない。フォークマングラフは、[[辺推移グラフ|辺推移的]]かつ正則な最小の無向グラフであるが、[[頂点推移グラフ|頂点推移的]]ではない<ref>Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 186-187, 1990</ref>。そのようなグラフは[[半対称グラフ]]と呼ばれ、1967 年にこのグラフを発見したフォークマンによって初めて研究された<ref>{{citation
 | first = J. | last = Folkman | authorlink=:en:Jon Folkman
 | title = Regular line-symmetric graphs
 | journal = Journal of Combinatorial Theory
 | volume =3 | year = 1967
 | issue = 3 | pages = 215–232
 | doi = 10.1016/S0021-9800(67)80069-3}}</ref>。

半対称グラフとしてのフォークマングラフは[[2部グラフ]]であり、その自己同型群は各二つの頂点からなる bipartition の集合上で推移的に作用する。フォークマングラフの彩色数を示している下の図においては、緑の頂点が赤の頂点へと写される自己同型は存在しないが、どのような赤の頂点も他の赤の頂点へと写すことができ、また、どのような緑の頂点も他の緑の頂点へと写すことが出来る。

フォークマングラフの[[特性多項式]]は <math>(x-4) x^{10} (x+4) (x^2-6)^4</math> である。

== ギャラリー ==
<gallery class="skin-invert-image">
ファイル:Folkman graph 4color edge.svg|フォークマングラフの{{仮リンク|辺彩色|en|Edge coloring|label=彩色指数}}は 4 である。
ファイル:Folkman graph.svg|フォークマングラフの[[グラフ彩色|彩色数]]は 2 である。
ファイル:Folkman Lombardi.svg|フォークマングラフは[[ハミルトングラフ|ハミルトン]]である。
</gallery>

== 参考文献 ==
{{reflist}}

{{DEFAULTSORT:ふおおくまんくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]