フォークマングラフ

フォークマングラフの概要

フォークマングラフ（Folkman graph）は、グラフ理論の中で特に注目される構造を持つグラフであり、ジョン・フォークマンの名に因んで名付けられました。このグラフは20個の頂点と40本の辺から構成され、4-正則な二部グラフとして知られています。つまり、全ての頂点が同じ数の辺を持つ特性を持っています。

このグラフの主な特性には、ハミルトン性、彩色数、彩色指数、半径、直径、内周といった重要な指標が含まれます。具体的には、フォークマングラフはハミルトンであり、彩色数は2、彩色指数は4、半径は3、直径は4、内周も4という数値を持ちます。また、このグラフは4-頂点連結かつ4-辺連結なパーフェクトグラフであるため、非常に安定した構造を持っています。

代数的性質

フォークマングラフの代数的な性質もまた興味深いものです。その自己同型群は、辺に関しては推移的に作用しますが、頂点に対してはそのように作用しません。これは、辺推移的かつ正則な最小の無向グラフでありながら、頂点推移的ではないことを意味しています。このような性質を持つグラフは、半対称グラフと呼ばれます。フォークマングラフは、1967年にフォークマンによって発見されたことから、半対称グラフの研究が始まりました。

フォークマングラフは二部グラフであり、自己同型群が二つの頂点からなる分割集合上で推移的に作用することが特徴的です。具体的には、緑の頂点が赤の頂点へと写されることはありませんが、任意の赤の頂点は他の赤の頂点に写ることができ、同様に緑の頂点も他の緑の頂点に写ることが可能です。このような関係性は、フォークマングラフの彩色数を視覚的に理解する上で重要な要素となります。

さらに、フォークマングラフの特性多項式は、以下のように表されます。

$$
(x - 4)x^{10}(x + 4)(x^{2} - 6)^{4}
$$

この多項式は、フォークマングラフの構造の数学的な特性を示す重要な役割を果たしています。

まとめ

フォークマングラフは、数学のグラフ理論において独自の位置を占めており、その特性や性質は多くの研究者にとって興味深いテーマとなっています。特に、その半対称性や自己同型群の特性は、グラフ理論のさまざまな応用に貢献しています。フォークマングラフは、今後もさらなる研究が期待される分野の一つであり、その理解は数学的な概念の深化に寄与することでしょう。

もう一度検索