フォークマングラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
フォークマングラフ
Folkman graph alt.svg
フォークマングラフ
命名者 ジョン・フォークマン
頂点 20
40
半径 3
直径 4
内周 4
彩色数 2
彩色指数 4
特性 ハミルトン
正則
2部
半対称
オイラー
完全
テンプレートを表示

数学グラフ理論の分野におけるフォークマングラフ: Folkman graph)とは、ジョン・フォークマン英語版の名にちなむ、20個の頂点と40個の辺を含む 4-正則かつ2部なあるグラフのことを言う[1]

フォークマングラフはハミルトンであり、彩色数は 2、彩色指数は 4、半径は 3、直径は 4、内周は 4 である。4-頂点連結かつ 4-辺連結完全グラフでもある。

代数的性質[編集]

フォークマングラフの自己同型群は、その辺上では推移的に作用するが、頂点上ではそのように作用しない。フォークマングラフは、辺推移的かつ正則な最小の無向グラフであるが、頂点推移的ではない[2]。そのようなグラフは半対称グラフと呼ばれ、1967 年にこのグラフを発見したフォークマンによって初めて研究された[3]

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

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

ギャラリー[編集]

参考文献[編集]

  1. ^ Weisstein, Eric W., "Folkman graph" - MathWorld.(英語)
  2. ^ Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 186-187, 1990
  3. ^ Folkman, J. (1967), “Regular line-symmetric graphs”, Journal of Combinatorial Theory 3 (3): 215–232, doi:10.1016/S0021-9800(67)80069-3