CutsAndConnectivity

定义

分割集 (separating set)/ 点割 (vertex cut): 点集 $S\subset V(G)$ , 满足 $G-S$ 的不连通或只有一个顶点.

连通度 $\kappa(G)$ : 点割集合大小的最小值.

如果图 $G$ 的连通度至少为 k, 则称它是 k-连通的.

例

$\kappa(K_n)=n-1$

$\kappa(K_{n,m})=\min\{n,m\}$ .

$\kappa(G)\leqslant \delta(G)$ .

例

$\kappa(Q_k)=k$ .

定义

Harary graph $H_{k,n}$ , $V=\Z_n$ .

$k=2t,\ \forall x,y\in V$ , $x\leftrightarrow y \Leftrightarrow x-y\in\{\pm 1,\pm 2,\cdots,\pm t\}$ .
$k=2t+1\wedge n=2m$ , $\forall x,y\in V$ , $x\leftrightarrow y \Leftrightarrow x-y\in\{\pm 1,\pm 2,\cdots,\pm t,m\}$ .
$k=2t+1\wedge n=2m+1$ , $E(H_{k,n})=E(H_{k-1,n})\cup\{i\leftrightarrow i+m|0\leqslant i\leqslant m\}$ .

性质

$H_{k,n}$ 是 k-正则的当且仅当 $kn$ 是偶数.

定理 Harary

$\kappa(H_{k,n})=k$ .

Cuts and connectivity #