グラフ因数分解

グラフ理論では、グラフGの因子は全域サブグラフ、つまりGと同じ頂点セットを持つサブグラフです。グラフのk因子は全域k正則サブグラフであり、k因数分解はグラフの辺を互いに素なk因数に分割します。グラフGは、 k因数分解が可能な場合、 k因数分解可能であると言われます。特に、1 因数は完全マッチングであり、k正則グラフの 1 因数分解はk色による適切な辺彩色です。2因数は、グラフのすべての頂点にまたがる 閉路の集合です。

グラフが 1 因数分解可能である場合、それは正則グラフでなければなりません。ただし、すべての正則グラフが 1 因数分解可能であるわけではありません。k正則グラフは、彩色指数 kを持つ場合、1 因数分解可能です。このようなグラフの例には次のものがあります。

• 任意の正則二部グラフ。^[1] ホールの結婚定理は、k正則二部グラフには完全マッチングが含まれていることを示すために使用できます。次に、完全マッチングを削除して( k  −1)正則二部グラフを取得し、同じ推論を繰り返し適用します。
• 偶数個のノードを持つ完全グラフ（下記参照）。^[2]

ただし、彩色指数k + 1を持つk正則グラフもあり 、これらのグラフは 1 因数分解できません。このようなグラフの例には次のものがあります。

• 奇数のノードを持つ任意の正規グラフ。
• ピーターセングラフ。

完全グラフの 1 因数分解は、総当たりトーナメントのペアリングに対応します。完全グラフの 1 因数分解は、完全ハイパーグラフの 1 因数分解に関するバラニャイの定理の特殊なケースです。

偶数個の頂点を持つ完全グラフの 1 因数分解を構築する方法の 1 つは、 1 つを除くすべての頂点を正多角形に配置し、残りの頂点を中心に配置することです。 この頂点配置でグラフの 1 因数を構築する 1 つの方法は、中心から単一の多角形頂点への辺e を、 eに垂直な線上にあるすべての可能な辺とともに選択することです。 この方法で構築できる 1 因数は、グラフの 1 因数分解を形成します。

K ₂、K ₄、K ₆、K ₈ 、...の異なる 1 因数分解の数は、1、1、6、6240、1225566720、252282619805368320、98758655816833727741338583040、... です ( OEIS : A000438 )。

G を2 n 個のノードを持つk正則グラフとします。kが十分に大きい場合、G は1 因数分解可能であること が知られています。

• k  = 2 n − 1の場合 、G は完全グラフK _{2 n}であり、したがって 1 因数分解可能です (上記を参照)。
• k  = 2 n − 2の場合 、G はK _{2 n}から完全マッチングを取り除くことによって構築できます。この場合も、G は1 因数分解可能です。
• Chetwynd & Hilton (1985)は、k  ≥ 12 n /7の場合、Gは1因数分解可能であることを示しています。

1因数分解予想[ ^3]は、 k  ≈  nで十分であるという長年の予想である。正確に言えば、この予想は次のようになる。

• nが奇数かつk  ≥  nの場合、Gは 1 因数分解可能です。nが偶数かつk  ≥  n  − 1 の場合、Gは 1 因数分解可能です。

オーバーフル予想は1因数分解予想を意味します。

1 因数分解からの完全ペアは、その和がハミルトン閉路を誘導する1 因数のペアです。

グラフの完全な 1 因数分解( P1F) は、1 因数のすべてのペアが完全なペアであるという特性を持つ 1 因数分解です。完全な 1 因数分解は、完全なマッチング (1 因数とも呼ばれます) と混同しないでください。

1964年、アントン・コッツィグは、 n ≥ 2であるすべての完全グラフK _{2 nは}完全な1因数分解を持つと予想しました。これまでに、次のグラフは完全な1因数分解を持つことが知られています。^[4]

• 完全グラフの無限族K _{2 p}（pは奇素数）（アンダーソンと中村が独立に定義）
• 完全グラフの無限族K _{p +1}（pは奇数素数）
• 散発的な追加結果、K _{2 n} （ 2 n ∈ {16、28、36、40、50、126、170、244、344、730、1332、1370、1850、2198、3126、6860、12168、16808、29792}）が含まれます。いくつかの新しい結果がここに集められています。

完全グラフKn _{+ 1}が完全な1因数分解を持つ場合、完全二部グラフ Kn _{, nも完全な1}因数分解を持つ。^[5]

グラフが2因数分解可能である場合、ある整数kに対して2k正則でなければなりません。ジュリアス・ピーターセンは1891年にこの必要条件は十分条件でもあることを示しました。つまり、任意の2k正則グラフは2因数分解可能であるということです。^[6]

連結グラフが 2 k正則で辺の数が偶数の場合、2つの因子のそれぞれをオイラー巡回経路の辺の交互部分集合として選択することで、k因数分解されることもあります。^[7] これは連結グラフにのみ適用されます。連結されていない反例としては、奇数サイクルの互いに素な和集合、またはK _{2 k  +1}のコピーの和集合などがあります。

オーバーヴォルフアッハ問題は、完全グラフの同型部分グラフへの 2 因数分解の存在に関するものです。どの部分グラフでこれが可能かを問うものです。部分グラフが連結されている場合 (その場合、それはハミルトン閉路であり、この特殊なケースはハミルトン分解の問題です)、これは既知ですが、一般的なケースは未解決のままです。