k-頂点連結グラフ

数学のグラフ理論において、頂点集合 $V(G)$ を備えるグラフ $G$ が k-頂点連結（k-ちょうてんれんけつ、英: k-vertex-connected）あるいはk-連結であるとは、 k より少ない数の頂点を取り除いても依然として連結グラフであることを言う。つまり、点連結度がk以上のグラフのことである。代替的に、グラフがk-連結であるとは、それらを除いたときにグラフが非連結となるような頂点の最小部分集合の大きさが k であることを言う^[1]。

グラフが完全でないことと同値な定義は、任意の二つの頂点が k 独立な道 (点素パス) によって結ばれるときにグラフがk-連結であることである; メンガーの定理を参照されたい(Diestel 2005, p. 55)。しかしながら、完全グラフに対して、上述の二つの定義は異なるものとなる: n-頂点の完全グラフは、頂点を除去することに基づいた定義に従うとその連結度は非有界となるが、独立な道に基づいた定義に従うと、その連結度は n − 1 になる。そして、何人かの研究者は、連結度が n となるような代替的な定義を用いている^[1]。

1-頂点連結グラフは、連結であると言われ、2-頂点連結グラフは2重連結であると言われる。

グラフの頂点連結度あるいは単純に連結度とは、そのグラフ k-頂点連結であるような k の最大数のことを言う。

任意のk-次元凸ポリトープのスケルトン（英語版）は、 k-頂点連結グラフを形成する（バリンスキーの定理、Balinski 1961）。その部分的な逆として、シュタイニッツの定理（英語版）では、任意の3-頂点連結平面グラフは凸多面体のスケルトンを形成する、ということが述べられている。

注釈

^ ^a ^b Schrijver, Combinatorial Optimization, Springer

参考文献

この項目は、組合せ数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

[Schrijver-1] Schrijver, Combinatorial Optimization, Springer

[1]

k-頂点連結グラフ

目次

関連項目

数学的対象と性質

定理

問題

その他

注釈

参考文献