本文所指的图均为连通的无向简单图, 文章中未说明的符号和术语同文献[1].

设$v$ 是$G=(V, E)$ 的一个顶点, $N_G(v)$ 表示$v$ 在$G$ 中的邻点集合. 对任意的非空集合$S\subseteq V$, 记$N_{G}(S)=\bigcup\limits_{v\in S}N_{G}(v)$, $G$ 中顶点$v$ 的度记为$d(v)$, $G$ 的最大度记为$\Delta(G)$. 对任意的非空集合$E'\subseteq E$, 由$E'$ 导出的$G$ 的子图记为$G[E']$, 以$E'$ 为边集的$G$ 的支撑子图记为$G(E')$, $\lfloor x\rfloor$ 表示不大于$x$ 的最大整数, $\lceil x\rceil$ 表示不小于$x$ 的最小整数.

$G=(V, E)$ 的控制集是指$V$ 的一个子集$V'$, 使得对任意的$v\in V-V'$, 都存在某个$u\in V'$ 与$v$ 相邻. 图$G$ 的控制数是它的最小控制集中的顶点数, 记为$\gamma(G)$. 本文仅考虑一般的控制数.

Vizing在文 [2] 中指出给定控制数的一般图的最大边数.

引理 1.1 ^[2] 若图$G$ 有$n$ 个顶点并且$2\leq \gamma(G)\leq n$, 则

$ E(G)\leq\big\lfloor\frac{(n-\gamma(G))(n-\gamma(G)-2)}{2}\big\rfloor, $

图$G$ 可以达到上界当且仅当$G$ 是从$(n-\gamma(G)+2)$ 个顶点的完全图中去掉一个最小的边覆盖, 然后并上$\gamma(G)-2$ 个孤立点得到的图.

根据引理1.1 可知, 若$\gamma\geq3$ 并且$G$ 取最大可能的边数, 则$G$ 有孤立点, 因此是不连通的. Sanchis 在文 [3] 中得出了给定控制数的连通图的最大边数.

引理 1.2 ^[3] 设图$G$ 是有$n$ 个顶点的连通图. 若$3\leq \gamma(G)\leq \frac{n}{2}$, 则$G$ 的边数最多是$\begin{pmatrix} n-\gamma-1\\ 2 \end{pmatrix}$.

如果我们限制在二部分图中, 则有下面的结论在文 [4] 中给出.

引理 1.3 ^[4] 对于任意的二部图$G$, 有$\gamma(G)\leq|V|-\Delta(G)-\big\lceil\frac{|E|}{\Delta(G)}\big\rceil+2$.

引理 1.4 ^[4] 设$G$ 是有$n$ 个顶点且控制数为$\gamma(G)\geq2$ 的二部图, 则可以达到最大边数的图是一个$n-\gamma(G)+2$ 个顶点的几乎平衡的完全二部图与$\gamma(G)-2$ 个孤立点的并.

从引理1.4 可知, 若$\gamma(G)\geq3$, 则可以达到这个界的图是不连通的. 陈宏宇和张丽在文 [5] 中给出二部图$G$ 的最大度至少为$n-\gamma(G)+1$ 时的最大边数.

引理 1.5 ^[5] 设图$G$ 是有$n$ 个顶点的连通二部图且$\gamma(G)\geq3,\ \Delta(G)\geq n-\gamma(G)-1$, 则$|E(G)|\leq {\big\lfloor\frac{{(n-\gamma)}^2+4(n-\gamma)}{4}\big\rfloor}(\gamma(G)=3,n=8$ 除外$)$.

高超和侯新民在文 [6] 进一步给出给定控制数的二部图的最大边数.

引理 1.6 ^[6] 设$G=(V, E)$ 为$n$ 阶二部图, 控制数为$\gamma$, 则如下结论成立:

(1)$|E|\leq \big\lfloor(\frac {n-\gamma+2}{2})^2\big\rfloor$;

(2)若$\Delta(G) \neq \lfloor \frac{n-\gamma+2}{2} \rfloor$ 或$\big\lceil\frac{n-\gamma+2}{2}\big\rceil$, 则 $|E(G)|\leq \big\lfloor \frac{ (n-\gamma)^2+4(n-\gamma)}{4} \big\rfloor$.

本文将对给定控制数的边数达到上界$\big\lfloor(\frac {n-\gamma+2}{2})^2\big\rfloor$ 时的极大$n$ 阶连通二部图进行刻画.

以下用$G=(M\cup N, E)\cong K_{m,\ (m+k)}-E'$ 表示二部划分为$M$ 和$N$ 的$n$ 阶连通二部图, 其中$|M|=m,\ |N|=m+k=n-m,\ k\geq0$, $E'$ 表示从完全二部图$ K_{m,\ (m+k)}$ 中删去的边数的集合.

引理 2.1  设$G=(M\cup N, E)\cong K_{m,\ (m+k)}-E'$ 是$n$ 阶连通二部图, 且$\gamma(G)=2$, 则$|E(G)|=\big\lfloor (\frac{n}{2})^2\big\rfloor\Leftrightarrow G\cong K_{\lfloor \frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$.

证 首先证明必要性. 设$G=(M\cup N, E)\cong K_{m,\ (m+k)}-E'$ 是$n$ 阶连通二部图, 则有

$ n=2m+k,\ |E(G)|=m(m+k)-|E'|\leq m(m+k). $

因为$|E(G)|=\big\lfloor (\frac{n}{2})^2\big\rfloor=\big\lfloor(\frac{2m+k}{2})^2\big\rfloor=m^2+mk+\big\lfloor\frac{k^2}{4}\big\rfloor\geq m(m+k)$, 所以$|E(G)|=m(m+k),\ k=0$ 或$1$, 从而得$G\cong K_{\lfloor \frac{n}{2}\rfloor ,\ \lceil\frac{n}{2}\rceil}$.

再证明充分性. 因为$G\cong K_{\lfloor \frac{n}{2}\rfloor,\ \lceil\frac{n}{2}\rceil}$, 所以不论$n$ 为奇数或偶数, 都有$|E(G)|=\lfloor \frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil=\lfloor (\frac{n}{2})^2\rfloor$, 并且完全二部图的控制数为$2$, 故充分性得证.

引理 2.2 设$G=(M\cup N, E)\cong K_{m,\ (m+k)}-E'$ 是$n$ 阶连通二部图, 且$\gamma(G)=3,\ |E(G)|=\lfloor(\frac{n-1}{2})^2\rfloor$, 则有如下结论:

(1)$G[E']$ 的每个连通分支中的边数均不小于$2$;

(2)$|E'|=m,\ k=0, 1, 2$, 且对于任意的$u\in M$, 均有$d_{G[E']}(u)=1$.

证 设$G=(M\cup N, E)\cong K_{m,\ (m+k)}-E'$ 是$n$ 阶连通二部图, 则有$n=2m+k,\ |E(G)|=m(m+k)-|E'|$. 假设存在$G[E']$ 的一个连通分支的边数为$1$, 那么与该边关联的两个顶点即为$G$ 的一个控制集, 与$\gamma(G)=3$ 矛盾.

一方面, $|E'|=m(m+k)-|E(G)|=m(m+k)-\big\lfloor(\frac{n-1}{2})^2\big\rfloor=m-\big\lfloor(\frac{k-1}{2})^2\big\rfloor\leq m.$

另一方面, 因为$\gamma(G)=3$, 所以$E'\neq \varnothing$, 且$|E'|\geq m$. 否则存在点$u\in M,\ v\in N$, 使得$u,\ v$ 均不与$E'$ 中的边关联, 从而$\{ u, v\}$ 为$G$ 的一个控制集, 与$\gamma(G)=3$ 矛盾. 综上可得$|E'|=m,\ k=0,1,2$.

当$k=1$ 或$2$, 即$|N|>|M|$ 时, 由于$|E'|=m$, 若存在$u\in M$, 且$u$ 不与$E'$ 中的边关联, 则也存在$v\in N$, 使得$v$ 也不与$E'$ 中的边关联, 从而$\{ u,v\}$ 为$G$ 的一个控制集, 与$\gamma(G)=3$ 矛盾, 所以对任意的$u\in M,\ d_{G[E']}(u)=1$.

当$k=0$, 即$|N|=|M|$ 时, 若存在$u\in M$ 使$u$ 不与$E'$ 中的边关联, 则对任意的$v\in N,\ d_{G[E']}(v)=1$. 否则由于$G[E']$ 中的每个连通分支中的边数均不小于$2$ 可知, 若存在一点$v\in N$, 使得$v$ 不与$E'$ 中的边关联, 则$\{u,v\}$ 为$G$ 的一个控制集, 与$\gamma(G)=3$ 矛盾. 由于$|M|=|N|$, 故将集合$M$ 与集合$N$ 对换, 从而得对任意的$u\in M,\ d_{G[E']}(u)=1$.

综上可得$|E'|=m,\ k=0, 1, 2$, 且对于任意的$u\in M$, 均有$d_{G[E']}(u)=1$.

引理 2.3 设$G=(M\cup N, E)\cong K_{m,\ (m+k)}-E'$ 是$n$ 阶连通二部图, 且$\gamma(G)\geq4,|E(G)|=\big\lfloor(\frac{n-\gamma+2}{2})^2\big\rfloor$, 则有

$|E'|= m(\gamma-2),\ k=\gamma-3, \gamma-2, \gamma-1,$

且对于任意的$u\in M$, 有$d_{G(E')}(u)=\gamma-2$.

证 设$G=(M\cup N, E)\cong K_{m,\ (m+k)}-E'$ 是$n$ 阶连通二部图, 则有

$\begin{eqnarray*} &&n=2m+k,\ |E(G)|=m(m+k)-|E'|,\\ &&|E'|=m(m+k)-\big\lfloor(\frac{2m+k-\gamma +2}{2}\big)^2\big\rfloor=m(\gamma-2)-\big\lfloor(\frac{k-\gamma +2}{2})^2\big\rfloor\leq m(\gamma-2). \end{eqnarray*}$

假设$|E'|<m(\gamma-2)$, 则存在$u\in M$, 使得$d_{G(E')}(u)\leq \gamma-3$. 任取$x\in M$ 且

$\begin{equation*} d_{G(E')}(x)=\min\{d_{G(E')}(u)|u\in M\}. \end{equation*}$

令

$\begin{equation*} Y=N_{G(E')}(x),\ X=\bigcap\limits_{y\in Y}N_{G(E')}(y), \end{equation*}$

则$X\cup Y$ 是$G$ 的一个控制集, 因图$G$ 的控制数为$\gamma$, 故$|X|\geq\gamma-|Y|$. 对于任意的$y'\in N-Y$, 令

$\begin{equation*} Z(y')=N_{G(E')}(y')\cap X, \end{equation*}$

因为$\{x,y'\}\cup Z(y')\cup Y$ 是$G$ 的一个控制集, 且图$G$ 的控制数为$\gamma$, 所以$|Z(y')|\geq\gamma-2-|Y|$. 于是有

$\begin{align*} (m-|X|)|Y| \leq&\sum \limits_{x'\in M-X}d_{G(E')}(x')\\ \leq&|E'|-(\gamma-2-|Y|)(m+k-|Y|)-|X||Y|\\ =&m(\gamma-2)-\big\lfloor(\frac{k-\gamma +2}{2})^2\big\rfloor-m(\gamma-2)\\&+m|Y|+(\gamma-2-|Y|)(|Y|-k)-|X||Y|\\ =&(|Y|-k)(\gamma-2)+|Y|(m+k-|Y|-|X|)-\big\lfloor(\frac{k-\gamma +2}{2})^2\big\rfloor\\ =&(m-|X|)|Y|-(|Y|-\frac{k+\gamma-2}{2})^2+(\frac{k-\gamma+2}{2})^2-\big\lfloor(\frac{k-\gamma +2}{2})^2\big\rfloor\\ \leq&(m-|X|)|Y|. \end{align*}$

上式等号成立当且仅当

$-(|Y|-\frac{k+\gamma-2}{2})^2+(\frac{k-\gamma+2}{2})^2-\big\lfloor(\frac{k-\gamma +2}{2})^2\big\rfloor=0,$

并且在$G(E')$ 中$M'=(M-X)\cup \{x\}$ 中每一点的度均为$|Y|,\ N-Y$ 中每一点在$X$ 中的度恰为$\gamma-2-|Y|$. 对于任意的$y'_1,\ y'_2\in N-Y$, 令

$\begin{equation*} |N_{G(E')}(y'_1)\cap N_{G(E')}(y'_2)\cap X|=l_{(y'_1, y'_2)}, \end{equation*}$

则$\{y'_1, y'_2, x\}\cup Y\cup(N_{G(E')}(y'_1)\cap N_{G(E')}(y'_2)\cap X)$ 为$G$ 的一个控制集, 且图$G$ 的控制数为$\gamma$, 所以$l_{(y'_1, y'_2)}\geq\gamma-3-|Y|$. 又对于任意的$y'\in N-Y,\ |N_{G(E')}(y')\cap X|=\gamma-2-|Y|$, 由$G$ 是连通的可得$l_{(y'_1, y'_2)}=\gamma-3-|Y|$, 进而得$|X|-1=\big|\bigcup \limits _{y'\in N-Y}N_{G(E')}(y'))\cap X\big|=\gamma-1-|Y|$, 即$|X|=\gamma-|Y|$. 选取$x'\in M-X$, 令

$\begin{equation*} Y'=N_{G(E')}(x'),\ X'=\bigcap\limits_{y'\in Y'}N_{G(E')}(y') \end{equation*}$

且$Y'\neq Y$, (这样的$x'$ 必存在, 否则$G$ 有孤立点). 因为$|N_{G(E')}(x)|=|N_{G(E')}(x')|=|Y|$, 则通过之前对$x$ 的讨论, 可得$|Y'|=|Y|,\ |X'|=|X|$. 因为$Y'\neq Y$, 所以$|Y'\cap Y|\leq|Y|-1$, 进而存在$y'\in Y'-(Y\cap Y')$, 使得

$|N_{G(E')}(y')\cap X|=\gamma-2-|Y|,$

所以$|X'\cap X|\leq\gamma-2-|Y|$, 且存在

$x_1\in X-(X'\cap X)-\{x\},\ x'_1\in X'-(X'\cap X)-\{x'\}.$

当$|Y'\cap Y|=|Y|-1$ 时, 若$N=Y'\cup Y$, 由于$|X|+|Y|=\gamma$, 可得$|N|+|X|=\gamma+1$. 若$|X|=1, |N|=\gamma$, 则$|M|=|N|=\gamma$, 且$\{x\}\cup Y$ 为$G$ 的一个控制集. 由于$G$ 的控制数为$\gamma$, 从而有$|Y|+1\geq\gamma$, 与$|Y|\leq\gamma-3$ 矛盾. 若$|X|>1$, 则$|N|<\gamma$ ,与$|N|\geq\gamma$ 矛盾, 故存在一点$y_1\in N-(Y\cap Y')$ , 且$|N_{G(E')}(y_1)\cap (X\cap X')|=\gamma-3-|Y|,$ 否则与$G$ 为连通图矛盾. 由于$\big|N_{G(E')}(y_1)\cap X'\big|=\gamma-2-|Y|$, 故$y_1$ 在$G(E')$ 中, 与$X'-(X'\cap X)-\{x'\}$ 中一点相邻, 这与$|N_{G(E')}(x'_1)|=|Y'|=|Y|$ 矛盾.

当$|Y'\cap Y|<|Y|-1$ 时, 存在$y_1,\ y_2\in Y-(Y\cap Y')$, 因为$\big|N_{G(E')}(y_1)\cap N_{G(E')}(y_2)\cap X'\big|=\gamma-3-|Y|,$ 所以存在$x''\in X'-(X'\cap X)-\{x'\}$ 在$G(E')$ 中, 与$y_1,\ y_2$ 中至少一个点相邻, 这与$|N_{G(E')}(x'_1)|=|Y'|=|Y|$ 矛盾.

所以有$|E'|=m(\gamma-2),\ k=\gamma-3, \gamma-2, \gamma-1$, 且对任意的$u\in M,\ d_{G(E')}(u)\geq\gamma-2$. 因为$\sum \limits_{u\in M}d_{G(E')}(u)=m(\gamma-2)$, 所以对任意的$u\in M,\ d_{G(E')}(u)=\gamma-2$.

下面将刻画对于给定控制数为$\gamma$ 的连通二部图边数达到上界$\lfloor (\frac{n-r+2}{2})^2\rfloor$ 时图的结构.

令

$\begin{eqnarray*} \Gamma_m^3&=&\{G=(M\cup N, E)\cong K_{m,\ (m+k)}-E'|M=\{u_1, u_2, \cdots, u_{m-1}, u_m\},\\ N&=&\{v_1, \cdots, v_l, v_{l+1}, \cdots, v_{m+k}\},\\ E'&=&\{u_iv_{l+1}|i=1, 2, \cdots, k_1\}\cup \{u_iv_{l+2}|i=k_1+1, \cdots, k_2\} \cup \cdots \\ &&\cup \{u_iv_{m+k}|i=k_{m+k-l-1}+1, \cdots, m\}, \end{eqnarray*}$

其中 $2\leq m+k-l\leq \lfloor \frac{m}{2}\rfloor,\ k=0,1,2, k_1\geq2,\ k_{i+1}-k_i\geq2, (i=1, 2, \cdots, m+k-l-2),\ m-k_{m+k-l-1}\geq2\}.$

定理 2.4 设$G=(M\cup N, E)\cong K_{m,\ (m+k)}-E'$ 是$n$ 阶连通二部图, 且$\gamma(G)=3$, 则$|E(G)|=\lfloor (\frac{n-1}{2})^2\rfloor \Leftrightarrow G\in \Gamma_m^3$.

证 先证明必要性. 由引理2.2 知$|E'|=m$, 对于任意的$u\in M,\ d_{G[E']}(u)=1$, 且$G[E']$ 的每个连通分支中的边数均不小于$2$, 所以在$G[E']$ 中存在孤立点, 且若$v\in N$ 在$G[E']$ 中与$M$ 中的点相邻, 则$d_{G[E']}(v)\geq2$. 若$d_{G[E']}(v)=m$, 则$v$ 在$G$ 中是孤立点, 与$G$ 为二部连通图矛盾, 于是$G[E']$ 中最少有两个连通分支, 最多有$\lfloor\frac{m}{2}\rfloor$ 个连通分支. 设$N_t=\{v\in N|d_{G[E']}(v)\geq2\},$ 则$2\leq |N_t|\leq \lfloor\frac{m}{2}\rfloor$, 且$N'=N-N_t$ 中的每个点在$G$ 中与$M$ 中的所有点均相邻. 由于任意的$u\in M,\ d_{G[E']}(u)=1$, 因此对任意的$v_1,\ v_2\in N_t$, 有$N_{G[E']}(v_1)\cap N_{G[E']}(v_2)=\varnothing$. 综上$G\in\Gamma_m^3$.

再证明充分性. 设$G\in\Gamma_m^3$ 且$G\cong K_{m,\ (m+k)}-E'$ 是$n$ 阶连通二部图, 则有

$ n=2m+k,\ k=0,1,2,\ |E'|=m,\ |E(G)|=m(m+k)-m=m(m+k-1) $

且$G[E']$ 中每个连通分支中的数不小于$2$.

$\begin{align*} \mbox{当}k&=0\mbox{时},\ |E(G)|=m(m-1)=\big\lfloor(\frac{2m-3+2}{2})^2\big\rfloor=\big\lfloor (\frac{n-1}{2})^2\big\rfloor,\\ \mbox{当}k&=1\mbox{时},\ |E(G)|=m^2=\big\lfloor(\frac{2m+1-3+2}{2})^2\big\rfloor=\big\lfloor (\frac{n-1}{2})^2\big\rfloor,\\ \mbox{当}k&=2\mbox{时},\ |E(G)|=m(m+1)=\big\lfloor(\frac{2m+2-3+2}{2})^2\big\rfloor=\big\lfloor (\frac{n-1}{2})^2\big\rfloor, \end{align*}$

所以$|E(G)|=\lfloor (\frac{n-1}{2})^2\rfloor$. 假设$\gamma(G)=2$, 令$\{u, v\}$ 是$G$ 的一个控制集, 则$u,\ v\in G[E']$ 且$N_G(u)\cup N_G(v)=M\cup N-\{u, v\}$, 从而$G[E']$ 中有一个连通分支只含一条边, 与$G[E']$ 的每个连通分支中的边数均不小于$2$ 矛盾, 所以$\gamma(G)\geq3$, 又$\{v_{m+k}, v_{m+k-1}, u_1\}$ 为$G$ 的一个控制集, 从而$\gamma(G)=3$.

例 2.5 当$\gamma(G)=3,\ |M|=7,\ |N|=8,\ k=1$ 时, 此时的极大图如图 1, 图中实点为控制点.

令

$\begin{eqnarray*} \Gamma_m^\gamma&=&\{G=(M\cup N, E)\cong K_{m,(m+k)}-E'|M=\{u_1, \cdots, u_m\},\\ N&=&\{v_1, \cdots, v_m, v_{m+1}, \cdots, v_{m+k}\},\\ E&=&\{u_iv_j|i=1, \cdots, m;\ j=1, \cdots, m+k-(\gamma-1)\}\cup \{u_iv_{m+k-(\gamma-2)}|i=1,\cdots k_1\}\\ &&\cup \{u_iv_{m+k-(\gamma-3)}|i=k_1+1,\cdots,k_2\}\cup\cdots\cup\{u_iv_{m+k}|i=k_{\gamma-2}+1, \cdots, m\}, \end{eqnarray*}$

其中$k=\gamma-3, \gamma-2, \gamma-1,\ k_1\geq2,\ k_{i+1}-k_i\geq2, (i=1,\cdots, \gamma-3),\ m-k_{\gamma-2}\geq2\}.$

定理 2.6 设$G=(M\cup N, E)\cong K_{m,\ (m+k)}-E'$ 是$n$ 阶连通二部图, 且$\gamma(G)=\gamma\geq4$, 则$|E(G)|=\big\lfloor(\frac{n-\gamma +2}{2})^2\big\rfloor \Leftrightarrow G\in \Gamma_m^\gamma$.

证 先证明必要性. 由引理2.3 知$|E'|=m(\gamma-2)$ 且任意的$u\in M,\ d_{G(E')}(u)=\gamma-2$ 且$k=\gamma-3, \gamma-2, \gamma-1$. 对任意的$u_1,\ u_2\in M$, 令

$ N'=N_{G(E')}(u_1)\cap N_{G(E')}(u_2), $

假设$|N'|=l_{(u_1, u_2)}\leq \gamma-4$. 若$l_{(u_1,u_2)}=0$, 即$N'=\varnothing$, 则有 \begin{equation*} m+k>m(\gamma-2)\geq 2m. \end{equation*} 解得$k>m$, 但$m\geq \gamma$, 矛盾于$k\leq \gamma-1$, 因此$l_{(u_1, u_2)}\geq 1$. 令

$\begin{equation*} X=\bigcap \limits_{v'\in N'}N_{G(E')}(v')-\{u_1\}, \end{equation*}$

对任意的$v\in N-N'$,令

$\begin{equation*} l(v)=|N_{G(E')}(v)\cap X|. \end{equation*}$

因为$(N_{G(E')}(v)\cap X)\cup N'\cup \{u_1, u_2, v\}$ 是$G$ 的一个控制集, 且图$G$ 的控制数为$\gamma$, 所以$l(v)\geq \gamma-3-l_{(u_1,u_2)}$. 由于

$\begin{equation*} \sum \limits_{v\in N-N'}l(v)+l_{(u_1,u_2)}|X|=(\gamma-2)|X|, \end{equation*}$

所以

$\begin{equation*} (\gamma-3-l_{(u_1,u_2)})(m+k-l_{(u_1,u_2)})+l_{(u_1,u_2)}|X|\leq (\gamma-2)|X|, \end{equation*}$

化简得

$\begin{equation}\label{22} (2+l_{(u_1,u_2)}-\gamma)(l_{(u_1,u_2)}+|X|-m-k)\leq m+k-l_{(u_1,u_2)}. \end{equation}$

(2.1)

因为$X\cup\{u_1\}\cup N'$ 是$G$ 的一个控制集, 且图$G$ 的控制数为$\gamma$, 所以$l_{(u_1,u_2)}\geq\gamma-|X|-1$, 即$|X|\geq \gamma-l_{(u_1,u_2)}-1\geq3$ . 由式(2.1) 可知

$\begin{equation*} (2+\gamma-|X|-1-\gamma)(\gamma-|X|-1+|X|-m-k)+\gamma-|X|-1\leq m+k, \end{equation*}$

整理得

$\begin{equation}\label{23} (1-|X|)(\gamma-1-m-k)+\gamma-|X|-1\leq m+k. \end{equation}$

(2.2)

当$k=\gamma-1$ 时, 带入式(2.2) 可得

$\begin{equation*} (1-|X|)(\gamma-1-m-\gamma+1)+\gamma-|X|-1\leq m+\gamma-1, \end{equation*}$

整理得

$\begin{equation}\label{24} (|X|-2)(m-1)\leq 2. \end{equation}$

(2.3)

因为$|X|\geq3$, 所以$|X|-2\geq1$. 由于$m\geq\gamma\geq4$, 故$m-1\geq3$. 所以 式(2.3) 不成立.

当$k=\gamma-2$ 时, 带入式(2.2) 可得

$\begin{equation*} (1-|X|)(\gamma-1-m-\gamma+2)+\gamma-|X|-1\leq m+\gamma-2, \end{equation*}$

整理得

$\begin{equation*} (|X|-2)(m-2)\leq 2. \end{equation*}$

由于$|X|-2\geq1,\ m-2\geq2$, 所以有

$ \begin{cases} |X|-2=1,\\ m-2=2, \end{cases} $

解得$|X|=3,\ m=4$, 此时$N'$ 中的点在$G$ 中为孤立点, 与$G$ 是连通图矛盾.

当$k=\gamma-3$ 时, 带入式(2.2) 可得

$\begin{equation*} (1-|X|)(\gamma-1-m-\gamma+3)+\gamma-|X|-1\leq m+\gamma-3, \end{equation*}$

整理得

$\begin{equation*} (|X|-2)(m-3)\leq 2. \end{equation*}$

由于$|X|-2\geq1, m-3\geq1$, 所以有

$ \begin{cases} |X|-2=2,\\ m-3=1, \end{cases} \mbox{或者} \begin{cases} |X|-2=1,\\ m-3=2. \end{cases} $

前式解得$|X|=4,\ m=4$, 与$m>|X|$ 矛盾. 后式解得$|X|=3,\ m=5$, 从而有$\gamma(G)\leq5,\ l_{(u_1, u_2)}\leq1$. 由于$\gamma(G)\geq4,\ l_{(u_1, u_2)}\geq1$, 进而得$\gamma(G)=5,\ l_{(u_1, u_2)}=1,\ k=2,\ |N|=7$. 因为任意的$u_1,\ u_2\in M,\ |N_{G(E')}(u_1)\cap N_{G(E')}(u_2)|=1$, 且$|N_{G(E')}(u_1)|=\gamma-2=3$, 所以$\{u_1\}\cup X$ 中这四个点在$G(E')$ 中还要与$N$ 中除共邻点外的$8$ 个点相邻, 故$|N|\geq9$ 与$|N|=7$ 矛盾.

综上可得$l_{(u_1,u_2)}\geq\gamma-3$, 即任意的$u_1,\ u_2\in M,\ |N_{G(E')}(u_1)\cap N_{G(E')}(u_2)|\geq \gamma-3$. 由引理2.3 可知, 对任意的$u\in M$, 均有$|d_{G(E')}(u)|=\gamma-2$, 所以对任意的$u_1,\ u_2\in M$, 有

$\begin{equation*} \gamma-2\geq|N_{G(E')}(u_1)\cap N_{G(E')}(u_2)|\geq \gamma-3. \end{equation*}$

若任意的$u_1,\ u_2\in M,\ |N_{G(E')}(u_1)\cap N_{G(E')}(u_2)|=\gamma-2$, 则与$G$ 是连通图矛盾. 若任意的$u_1,\ u_2\in M,\ |N_{G(E')}(u_1)\cap N_{G(E')}(u_2)|=\gamma-3$, 则$|M|=\gamma-1$, 与$|M|\geq\gamma$ 矛盾. 故$M$ 中的一部分顶点, 其中任何两顶点在$G(E')$ 中共邻点的个数为$\gamma-2$, 另一部分顶点, 其中任何两顶点在$G(E')$ 中共邻点的个数为$\gamma-3$, 且

$ \big|\bigcap\limits_{u\in M}N_{G(E')}(u)\big|=\varnothing,\ \big|\bigcup\limits_{u\in M}N_{G(E')}(u)\big|=\gamma-1. $

$M$ 中的点与$N-N'$ 中$m+k-(\gamma+1)$ 个点在$G$ 中全相邻, 所以$N-N'$ 中$m+k-(\gamma+1)$ 个点只需用$M$ 中任意一个点便可控制, 而图$G$ 的控制数为$\gamma$, 故$N'$ 中$\gamma-1$ 个点需控制$M$ 中的所有点. 若在$G$ 中, $N'$ 中存在一点仅与$M$ 中的一个点相邻, 此时图$G$ 的控制数为$\gamma-1$, 与$\gamma(G)=\gamma$ 矛盾, 所以在$G$ 中, $N'$ 中的每个点与$M$ 中至少两个点相邻. 综上$G\in \Gamma_m^\gamma$.

再证明充分性. 设$G\in \Gamma_m^4$, 从而有$k=1,2,3,\ |E'|=2m$, 且

$\begin{align*} &|E(G)|=m(m+k)-2m=(m+k-2)m,\\ &\mbox{当}k=1\mbox{时},\ |E(G)|=m(m-1)=\big\lfloor(\frac{n-2}{2})^2\big\rfloor\\ &\mbox{当}k=2\mbox{时},\ |E(G)|=m^2=\big\lfloor(\frac{n-2}{2})^2\big\rfloor\\ &\mbox{当}k=3\mbox{时},\ |E(G)|=m(m+1)=\big\lfloor(\frac{n-2}{2})^2\big\rfloor \end{align*}$

所以$|E(G)|=\big\lfloor(\frac{n-2}{2})^2\big\rfloor$. 令$A=\{v_{m+k-2}, v_{m+k-1}, v_{m+k}\}$, 假设$\gamma(G)=3$. 为了控制$A$ 中所有点, 至少需要$3$ 个控制点, 若这$3$ 个控制点全在$A$ 中, 则无法控制$N-A$ 中的顶点, 所以这$3$ 个控制点不全在$A$ 中, 但此时无法控制$M$ 中的所有顶点, 所以$\gamma(G)\geq4$, 又$\{v_{m+k}, v_{m+k-1}, v_{m+k-2}, u_1\}$ 为$G$ 的一个控制集, 所以$\gamma(G)=4,\ |E(G)|=\big\lfloor(\frac{n-\gamma+2}{2})^2\big\rfloor$.

假设$\gamma>4$, 且结论对$\gamma-1$成立. 令

$ G=(M\cup N, E(G))\in \Gamma_m^\gamma,\ G'=(M\cup N', E(G')), $

其中

$ N'=N-\{v_{m+k}\},\ E(G')=(E(G)-\{v_{m+k}u|u\in M\})\cup \{v_{m+k-1}u|u\in N_{G}(v_{m+k})\}. $

于是$G'\in \Gamma_m^{\gamma-1}$, 由归纳假设知$|E(G')|=\big\lfloor(\frac{n-1-(\gamma-1)+2}{2})^2\big\rfloor$ 且$\gamma(G')=\gamma-1$, 进而有$|E(G)|=|E(G')|=\big\lfloor(\frac{n-1-(\gamma-1)+2}{2})^2\big\rfloor=\big\lfloor(\frac{n-\gamma+2}{2})^2\big\rfloor$. 令

$ B=\{v_{m+k}, v_{m+k-1}, \cdots, v_{m+k-(\gamma-2)}\}, $

假设$\gamma(G)=\gamma-1$. 为了控制$B$ 中所有点, 至少需要$\gamma-1$ 个控制点, 若这$\gamma-1$ 个控制点全在$B$ 中, 则无法控制$N-B$ 中的顶点, 所以这$\gamma-1$ 个控制点不全在$B$ 中, 但此时无法控制$M$ 中的所有顶点, 因此$\gamma(G)\geq\gamma-1$, 又$\{v_{m+k}, v_{m+k-1}, \cdots, v_{m+k-(\gamma-2)}, u_1\}$ 为$G$ 的一个控制集, 所以当$G\in \Gamma_m^\gamma$ 且$\gamma(G)=\gamma$时, 有$|E(G)|=\big\lfloor(\frac{n-\gamma+2}{2})^2\big\rfloor$.

由定理2.4 和2.6 的证明易得如下推论:

推论 2.7 设$G=(M\cup N, E)\cong K_{m,\ (m+k)}-E'$ 是$n$ 阶连通二部图, 且$\gamma(G)=\gamma,\ |E(G)|=\big\lfloor(\frac{n-\gamma +2}{2})^2\big\rfloor$, 则有$|M|\geq 2(\gamma-1),\ \Delta(G)=\big\lfloor \frac{n-\gamma+2}{2}\big\rfloor$ 或$\big\lceil\frac{n-\gamma+2}{2}\big\rceil$.