数学のグラフ理論におけるクネーザーグラフ（） とは、n 元集合のk元部分集合を各頂点に配し、互いに素な集合に対応する頂点を辺で結んだグラフのことを言う。1955年に初めて研究したマルティン・クネーザーの名にちなむ。
例 n 個の頂点を持つ完全グラフはクネーザーグラフ である。
クネーザーグラフ は として知られる。奇グラフ はピーターセングラフと同型である。
性質 クネーザーグラフは頂点推移的かつ辺推移的である。各頂点は必ず 個の隣を持つ。しかしながら、一般的にクネーザーグラフは強正則グラフではない。なぜならば、隣接していない頂点同士の複数のペアは、その対応する集合のペアの共通部分の大きさに依存して、共通に持つ近傍の数が異なるからである。
が予想したように、クネーザーグラフ の彩色数は必ず となる。例えば、ピーターセングラフはどのような特定の彩色に対しても三つの色を必要とする。 はこの事実を、の分野における位相的手法を用いることによって証明した。その後まもなく、 はボルスク・ウラムの定理とデヴィッド・ゲールの補題を用いることによって、簡単な証明を与え、さらに は簡略化ではあるが依然として位相的な証明を与えることによってを得た。また、 は純粋なを与えた。 であるなら、クネーザーグラフは常にハミルトン閉路を含む 。計算機的な研究によれば、 であるようなすべての連結なクネーザーグラフは、ピーターセングラフを除き、ハミルトンである 。 であるなら、クネーザーグラフは三角形を含まない。より一般的に、 であればクネーザーグラフは常に長さ4の閉路を含むが、 に近い値 n に対して、最も短い奇閉路は一定の長さを持たないことがある 。 連結クネーザーグラフ のは
クネーザーグラフ のグラフスペクトルは次のように与えられる: に対し、固有値 が得られる。ここで、その重複度は、 に対しては であり、 に対しては 1 となる。証明にはこの論文を参照されたい。
関連するグラフ は、n 元集合の k 元部分集合が頂点となり、その -元部分集合が一致するとき、各頂点が隣接するようなグラフである。 に対して、ジョンソングラフはクネーザーグラフ の補となる。ジョンソングラフは、と密接に関係している。それらはいずれもの名にちなむ。
一般化クネーザーグラフ とは、クネーザーグラフと頂点集合は同じものであるが、二つの頂点が連結するための必要十分条件が、それらに対応する集合が s 以下の共通部分を持つこと、であるようなグラフのことである 。したがって、 である。
2部クネーザーグラフ （bipartite Kneser graph） は、n 個の元の集まりから抽出される k 個の元および 個の元の集まりを頂点とするグラフである。二つの頂点が辺によって連結されているための必要十分条件は、一方の集合が他方の部分集合となっていることである。クネーザーグラフと同様に、2部クネーザーグラフは次数 でもって頂点推移的である。
2部クネーザーグラフは、 のとして構成される。それにおいては、各頂点のコピーが作られ、各辺は、対応する頂点のペアを結び付けている辺と入れ替えられている 。2部クネーザーグラフ はであり、2部クネーザーグラフ はである。
参考文献 . . . . . . . . . .
外部リンク