クネーザーグラフ

テンプレート:Infobox graph

数学のグラフ理論におけるクネーザーグラフ（テンプレート:Lang-en-short）テンプレート:Math とは、n 元集合のk元部分集合を各頂点に配し、互いに素な集合に対応する頂点を辺で結んだグラフのことを言う。1955年に初めて研究したマルティン・クネーザーの名にちなむ。

例

n 個の頂点を持つ完全グラフはクネーザーグラフテンプレート:Math である。

クネーザーグラフテンプレート:Math はテンプレート:仮リンクテンプレート:Math として知られる。奇グラフテンプレート:Math はピーターセングラフと同型である。

性質

クネーザーグラフは頂点推移的かつ辺推移的である。各頂点は必ず $(\binom{n - k}{k})$ 個の隣を持つ。しかしながら、一般的にクネーザーグラフは強正則グラフではない。なぜならば、隣接していない頂点同士の複数のペアは、その対応する集合のペアの共通部分の大きさに依存して、共通に持つ近傍の数が異なるからである。

テンプレート:Harvtxtが予想したように、クネーザーグラフテンプレート:Math の彩色数は必ずテンプレート:Math となる。例えば、ピーターセングラフはどのような特定の彩色に対しても三つの色を必要とする。テンプレート:Harvs はこの事実を、テンプレート:仮リンクの分野における位相的手法を用いることによって証明した。その後まもなく、テンプレート:Harvs はテンプレート:仮リンクとデヴィッド・ゲールの補題を用いることによって、簡単な証明を与え、さらにテンプレート:Harvtxt は簡略化ではあるが依然として位相的な証明を与えることによってテンプレート:仮リンクを得た。また、テンプレート:Harvtxt は純粋なテンプレート:仮リンクを与えた。
テンプレート:Math であるなら、クネーザーグラフは常にハミルトン閉路を含むテンプレート:Harv。計算機的な研究によれば、テンプレート:Math であるようなすべての連結なクネーザーグラフは、ピーターセングラフを除き、ハミルトンであるテンプレート:Harv。
テンプレート:Mathであるなら、クネーザーグラフは三角形を含まない。より一般的に、テンプレート:Math であればクネーザーグラフは常に長さ4の閉路を含むが、テンプレート:Math に近い値 n に対して、最も短い奇閉路は一定の長さを持たないことがあるテンプレート:Harv。
連結クネーザーグラフテンプレート:Math の直径テンプレート:Enlinkは
$⌈ \frac{k - 1}{n - 2 k} ⌉ + 1$ テンプレート:Harv

である。

クネーザーグラフテンプレート:Math のグラフスペクトルは次のように与えられる:

j = 0, . . ., k

に対し、固有値

λ_{j} = (- 1)^{j} (\binom{n - k - j}{k - j})

が得られる。ここで、その重複度は、

j > 0

に対しては

(\binom{n}{j}) - (\binom{n}{j - 1})

であり、

j = 0

に対しては 1 となる。証明にはこの論文を参照されたい。

参考文献

外部リンク

クネーザーグラフ

目次

例

性質

関連するグラフ

参考文献

外部リンク

ナビゲーションメニュー

クネーザーグラフ

例

性質

関連するグラフ

参考文献

外部リンク

ナビゲーション メニュー

検索

ナビゲーションメニュー