Cuts and connectivity
连通度 $\kappa(G)$: 点割集合大小的最小值. 如果图 $G$ 的连通度至少为 k, 则称它是 k-连通的.
定义 5.1.1
分割集 (separating set)/ 点割 (vertex cut): 点集 $S\subset V(G)$, 满足 $G-S$ 的不连通或只有一个顶点.
$\kappa(K_{n,m})=\min\{n,m\}$. $\kappa(G)\leqslant \delta(G)$.
例 5.1.2
$\kappa(K_n)=n-1$
例 5.1.3
$\kappa(Q_k)=k$.
定义 5.1.4
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\}$.
性质 5.1.5
$H_{k,n}$ 是 k-正则的当且仅当 $kn$ 是偶数.
定理 5.1.6 Harary
$\kappa(H_{k,n})=k$.