フォークマングラフ

フォークマングラフ
フォークマン（1967）の図1に倣った絵
名前の由来	ジョン・フォークマン
頂点	20
エッジ	40
半径	3
直径	4
胴回り	4
自己同型	5! · 2 5 = 3840
彩度数	2
色指数	4
属	3
本の厚さ	3
キュー番号	2
プロパティ	二分法 オイラー ハミルトニアン 通常 半対称
グラフとパラメータの表

数学のグラフ理論の分野において、フォークマングラフは20の頂点と40の辺を持つ4正則グラフである。これはすべての辺が他のすべての辺に向かう対称性を持つ正則二部グラフであるが、その二分割の2つの辺は互いに対称ではなく、可能な限り最小の半対称グラフとなっている。^[1]このグラフは1967年にこの特性のために構築したジョン・フォークマンにちなんで名付けられた。 ^[2]

フォークマングラフは、モジュラー演算を使用して構築することも、5頂点の完全グラフの分割された2倍として構築することもできます。その対称性の調査以外に、グラフ埋め込みの特定の問題に対する反例としても調査されてきました。

半対称グラフは、2 つの辺が互いに対称であるが、いくつかの 2 つの頂点は対称ではない正則グラフ (つまり、すべての頂点が同数の辺に接するグラフ) として定義されます。ジョン フォークマンは、対称条件は満たすが正則条件は満たさないグラフの例を示した E. ドーバーとフランク ハラリーの未発表の原稿を見て、1967 年の論文でこれらのグラフを定義し研究するインスピレーションを得ました。フォークマンによるこのグラフの元の構築は、 1 mod 4 に合同な素数に基づくモジュラー演算を使用した、より一般的な半対称グラフの構築の特殊なケースでした。このような素数ごとに、modとなる数があり、フォークマンはモジュラー演算を使用して、頂点を持つ半対称グラフを構築します。フォークマン グラフは、およびに対してこの構築を行った結果です。^[2]${\displaystyle p}$${\displaystyle r}$${\displaystyle r^{2}=-1}$${\displaystyle p}$${\displaystyle 2pr}$${\displaystyle p=5}$${\displaystyle r=2}$

フォークマングラフの別の構築は、5つの頂点を持つ完全グラフから始まります。 の10の辺のそれぞれに新しい頂点が置かれ、各辺が2辺のパスに細分化されます。次に、 の元の5つの頂点のそれぞれが2倍になり、同じ隣接頂点を持つ2つの頂点に置き換えられます。10個の細分頂点はフォークマングラフの2分割の片側を形成し、 の2倍になった頂点から来る10個の頂点の双子のペアは、2分割のもう一方の側を形成します。^{[3] [4]}${\displaystyle K_{5}}$${\displaystyle K_{5}}$${\displaystyle K_{5}}$${\displaystyle K_{5}}$

結果の各辺は の辺の半分を2倍したものから来ており、 はすべての半辺を他のすべての半辺に向かう対称性を持つため、結果は辺推移的です。 分割頂点は他のどの頂点とも双子ではなく、 から来る2倍の頂点とは異なるため、これは頂点推移的ではありません。[ ^3] 2つの頂点が同じ近傍を持つすべての4正則半対称グラフは、や八面体のグラフなどの4正則対称グラフを分割してから2倍にすることで、同じ方法で構築できます。ただし、双子の頂点を持たない、より大きな4正則半対称グラフも存在します。^{[4] [5]}${\displaystyle K_{5}}$${\displaystyle K_{5}}$${\displaystyle K_{5}}$${\displaystyle K_{5}}$

フォークマングラフの自己同型群（その対称性の群）は、 の対称性と、重複した頂点のペアを交換する方法を組み合わせたもので、合計 の対称性を持つ。この群はフォークマングラフの辺に対して推移的に作用するが（任意の辺を他の任意の辺に移動する対称性を含む）、頂点に対しては作用しない。フォークマングラフは、辺推移的かつ正則だが頂点推移的ではない最小の無向グラフである。^{[6]このようなグラフは}半対称グラフと呼ばれ、1967 年にフォークマンによって初めて研究され、20 頂点のグラフが発見された。このグラフは現在、彼の名にちなんで名付けられている。^[2]${\displaystyle 5!}$${\displaystyle K_{5}}$${\displaystyle 2^{5}}$${\displaystyle 5!\cdot 2^{5}=3840}$

すべての半対称グラフと同様に、フォークマングラフは二部グラフである。その自己同型群には、任意の頂点を二部グラフの同じ側にある任意の他の頂点に取る対称性が含まれるが、二部グラフの反対側に頂点を取る対称性は含まれない。フォークマングラフは頂点推移的ではないと直接主張することもできるが、これは群論的に説明することもできる。その対称性は、の分割点として構成される頂点に対して原始的に作用するが、 の頂点を倍増することによって構成される頂点に対しては原始的に作用する。すべての対称性は、倍増した頂点のペアを別の倍増した頂点のペアにマッピングするが、対称性によって保存される分割頂点のグループ化はない。^[7]${\displaystyle K_{5}}$${\displaystyle K_{5}}$

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

フォークマングラフにはハミルトン閉路があり、より強いハミルトン分解により2つのハミルトン閉路が形成される。他の2部グラフと同様に、その彩色数は2であり、彩色指数（同じ色の2つの辺が頂点で交わらないように辺を彩色するために必要な色の最小数）は最大次数に等しく、^[9]この場合は4である。例えば、このような彩色は、ハミルトン分解の各閉路に2色を交互に使用することで得られる。

の半径は 3、直径は 4 です。 が構成の二重頂点の 1 つである場合、他のすべての頂点は から最大 3 ステップ離れています。ただし、 の構成からのサブディビジョン頂点のペア ( の互いに素な辺から来ている) は、互いに 4 ステップ離れています。グラフには多くの 4 閉路が含まれているため、その内周は4 で、これは二部グラフで可能な最小値です。また、4頂点接続および 4辺接続です。そのツリー幅とクリーク幅はどちらも 5 です。^[10]${\displaystyle v}$${\displaystyle K_{5}}$${\displaystyle v}$${\displaystyle K_{5}}$

フォークマングラフの種数は3である。つまり、三重トーラスに埋め込むことはできるが、より単純な有向面には埋め込むことができない。^{[11] [12]}本の厚さは3であるが、各ページが対応するである「分散可能な」本の埋め込みには5ページが必要であり、正則グラフの分散可能な本の埋め込みには次数に等しいページ数のみが必要であるというフランク・バーンハートとポール・カイネンの予想を反証している。 ^[3]