2 主要结果
定理2.1 设 $G$是连通图, 则 $\gamma_{ssc}^\prime(G)=|E|-2\Longleftrightarrow G\in \{K_2, K_{m, n}, K_{m_1, m_2, \cdots, m_t}\}, $其中 $m\geq n\geq 2, t\geq 3$.
证 先证充分性.显然 $\gamma_{ssc}^\prime(K_2)=-1=1-2=|E|-2$.注意到 $K_{m, n}$, $K_{m_1, m_2, \cdots, m_t}$都不是空图, 再根据引言中的事实可知
| $
\gamma_{ssc}^\prime(K_{m, n})\leq |E|-2,
$ |
(1) |
| $
\gamma_{ssc}^\prime(K_{m_1, m_2, \cdots, m_t})\leq |E|-2.
$ |
(2) |
下面证明以上两个不等式都取等号.
设 $f$是 $K_{m, n}$的任意一个强符号圈控制函数, 则在 $f$下 $K_{m, n}$中至多有一条边取 $-1$.因为若有两条边取 $-1$, 则这两条边必在一个长度为4的圈 $C_4$中, 所以 $f(C_4)\leq 0$, 这与 $f$是 $K_{m, n}$的一个强符号圈控制函数相矛盾.所以 $f(E)=|E^+|-|E^-|=|E|-2|E^-|\geq |E|-2$.再结合(1) 式可知 $\gamma_{ssc}^\prime(K_{m, n})=|E|-2$.
设 $f$是 $K_{m_1, m_2, \cdots, m_t}$的任意一个强符号圈控制函数, 若在 $f$下有两条边 $e_1=u_1v_1$, $e_2=u_2v_2$取-1, 则 $u_1, v_1$两顶点分别在完全 $t$部图 $K_{m_1, m_2, \cdots, m_t}$的两部分 $X_{u_1}$、 $X_{v_1}$之中, $u_2, v_2$两顶点也分别在完全 $t$部图 $K_{m_1, m_2, \cdots, m_t}$的两部分 $X_{u_2}$、 $X_{v_2}$之中, 显然 $X_{u_1}\neq X_{v_1}$, $X_{u_2}\neq X_{v_2}$.若 $X_{u_1}=X_{u_2}$, 当 $u_1, u_2$重合时, 若 $v_1, v_2$在完全 $t$部图 $K_{m_1, m_2, \cdots, m_t}$的同一部分中, 则 $e_1, e_2$必在同一个四边形中, 这不可能, 若 $v_1, v_2$在完全 $t$部图 $K_{m_1, m_2, \cdots, m_t}$的不同部分中, 则 $e_1, e_2$必在同一个三角形中, 这也不可能.当 $u_1, u_2$不重合时, 显然 $X_{u_1}\neq X_{v_2}$, $X_{v_1}\neq X_{u_2}$, 所以 $u_1v_1u_2v_2u_1$是 $K_{m_1, m_2, \cdots, m_t}$的一个长度为4的圈且有两条边取 $-1$, 这是不可能的.同理 $X_{v_1}=X_{v_2}$也不可能.所以 $X_{u_1}\neq X_{u_2}$且 $X_{v_1}\neq X_{v_2}$, 但这时 $u_1v_1v_2u_2u_1$是一个长度为4的圈且有两条边取-1, 这也是不可能的.综上所述 $|E^-|\leq 1$.所以
| $
f(E)=|E|-2|E^-|\geq |E|-2.
$ |
(3) |
再结合(2) 式得 $\gamma_{ssc}^\prime(K_{m_1, m_2, \cdots, m_t})=|E|-2$.充分性证毕.
下面再证必要性.设
| $
\gamma_{ssc}^\prime(G)=|E|-2.
$ |
(4) |
不妨 $G\neq K_2$, 于是 $G$无悬挂边且有以下事实:
1) $G$的任意两边必在同一个长度为3或4的圈上, 否则若 $G$有两边既不在同一个3圈上又不在同一个4圈上, 令这两边取-1其他边都取+1, 则得 $G$的一个强符号圈控制函数 $f$, 使 $\gamma_{ssc}^\prime(G)\leq f(E)=|E|-4$, 这与(4) 式矛盾.
2) 对 $G$的任意两个不相邻顶点 $u, v$, 必有 $N(u)=N(v)$.否则若 $N(u)\neq N(v)$, 当 $N(u)\bigcap N(v)=\emptyset$时, 取 $u$的一条邻边 $uu_1$, $v$的一条邻边 $vv_1$, 这两边显然既不在同一个3圈上也不在同一个4圈上, 这与上面事实矛盾.当 $N(u)\bigcap N(v)\neq \emptyset$时, 设 $u_1\in N(u)\bigcap N(v)$, $u_2$是 $u$的邻点但不是 $v$的邻点, 则 $vu_1$和 $uu_2$两边既不在同一个3圈上也不在同一个4圈上, 这也与上面事实矛盾.所以 $N(u)=N(v)$.
设 $N_1$是图 $G$的一个最大独立集, 则 $N_1$中任何两点都不相邻, 所以 $N_1$中任意两点的邻集都相等.记 $N_2=V-N_1$, 把 $G[N_2]$中的边都去掉后, 得到一个完全二部图 $K_{|N_1|, |N_2|}$.若 $N_2$是 $G$的独立集, 则显然 $G=K_{|N_1|, |N_2|}$, 若 $N_2$不是 $G$的独立集, 则 $G[N_2]$中必有边.设 $N_3$是 $G[N_2]$的最大独立集, 则 $N_3$必是 $G$的独立集, 所以 $N_3$中任意两点的邻集都相等.令 $N_4=N_2-N_3$, 把 $G[N_4]$中的边都去掉后, 得到一个完全三部图 $K_{|N_1|, |N_3|, |N_4|}$.若 $N_4$是 $G$的独立集, 则 $G=K_{|N_1|, |N_3|, |N_4|}$, 若 $N_4$不是 $G$的独立集, 则 $G[N_4]$中必有边.设 $N_5$是 $G[N_4]$的最大独立集, 则 $N_5$必是 $G$的独立集, 所以 $N_5$中任意两点的邻集都相等.令 $N_6=N_4-N_5$, 把 $G[N_6]$中的边都去掉后, 得到一个完全四部图 $K_{|N_1|, |N_3|, |N_5|, |N_6|}$.若 $N_6$是 $G$的独立集, 则 $G=K_{|N_1|, |N_3|, |N_5|, |N_6|}$, 若 $N_6$不是 $G$的独立集, 则继续一步步分解下去, 最后必把 $G$分解为一个完全多部图, 定理证毕.
定理2.2 设 $G$是个有 $n$个顶点 $m$条边的图, 则 $\gamma_{ssc}^\prime(G)\geq m-2n+2$, 当且仅当 $G$是树时取等号.
证 设 $f$是图 $G$的任意一个强符号圈控制函数, 则 $f(E)=|E^+|-|E^-|=|E|-2|E^-|$.把图 $G$的正边都去掉后必得一个无圈图, 所以 $|E^-|\leq n-1$, 这样
| $
f(E)=m-2|E^-|\geq
m-2(n-1)=m-2n+2.
$ |
所以 $\gamma_{ssc}^\prime(G)\geq m-2n+2$.
当 $\gamma_{ssc}^\prime(G)=m-2n+2$时, 设 $f$是图 $G$的一个取值最小的强符号圈控制函数, 则必有 $|E^-|=n-1$, 否则若 $|E^-|<n-1$, 则 $f(E)=m-2|E^-|>m-2n+2$矛盾.因 $G[E^-]$中无圈, 所以 $G[E^-]$是树, 所以 $G$中无正边.否则树 $G[E^-]$中连接这条正边的两端点的路和这条正边构成圈 $C$, 使 $f(C)\leq 0$矛盾.所以 $G=G[E^-]$是树.证毕.
定理2.3 设 $T_n$是有 $n$个顶点的树, 则 $\gamma_{ssc}^\prime(T_n+K_1)=2n-1-2\alpha^\prime(T_n)$, 其中 $\alpha^\prime(T_n)$表示 $T_n$的边独立数.
证 设 $M$是 $T_n$的一个最大匹配, 令 $f(e)=-1, e\in M$, $f(e)=1, e\notin M$.
下面证明这样定义的 $f$是 $T_n+K_1$的一个强符号圈控制函数.
设 $C$是 $T_n+K_1$的任意一个圈, 则 $C$一定过 $K_1$.记 $C$上 $K_1$的两关联边分别为 $K_1u$, $K_1v$.显然 $u, v$都是 $T_n$的点, 不妨 $T_n$中连接 $u, v$两点的路为 $P=uv_1v_2\cdots v_kv$, 则 $C=uv_1v_2\cdots v_kvK_1u$.当 $k$为偶数时, $P$的最大匹配含有 $\frac{k+2}{2}$个边, 因此 $P$上至多有 $\frac{k+2}{2}$个 $-1$, 所以 $f(C)\geq k+1-2\frac{k+2}{2}+2=1$.当 $k$为奇数时, $P$的最大匹配含有 $\frac{k+1}{2}$个边, 因此 $P$上至多有 $\frac{k+1}{2}$个 $-1$, 所以 $f(C)\geq k+1-2\frac{k+1}{2}+2=2$.这样我们就证明了 $f$是 $T_n+K_1$的一个强符号圈控制函数, 所以
| $
\gamma_{ssc}^\prime(T_n+K_1)\leq f(E)=2n-1-2\alpha^\prime(T_n).
$ |
(5) |
下面再证明 $\gamma_{ssc}^\prime(T_n+K_1)\geq 2n-1-2\alpha^\prime(T_n)$.
设 $f$是 $T_n+K_1$的任意一个强符号圈控制函数, 令 $A=\{e|f(e)=-1, e\in T_n\}$, 显然 $T_n$中任意两条负边不能邻接, 于是 $A$构成 $T_n$的一个匹配.若 $E(K_1)$中有一条负边 $K_1v$, 则 $v$在 $T_n$中的关联边全是正边.对 $v$的任意一个邻点 $v_1$, $v_1$的关联边也全是正边.现在把 $vv_1$改为负边, $K_1v$改为正边, 其他边的权不变, 这样得到的函数 $f_1$仍是 $T_n+K_1$的一个强符号圈控制函数.这只要证明过边 $vv_1$且不过边 $K_1v$的圈 $C$的权都大于等于1即可.若 $d_{T_n}(v)=1$, 这样的圈当然不存在.若 $d_{T_n}(v)\geq 2$, 当这个圈过 $v$点的 $T_n$一条悬挂边 $vu_1$时,
| $
f_1(C)=f(C-vu_1-u_1K_1+vK_1)-1+2\geq 2,
$ |
当这个圈过 $v$点的两条边 $vu_1$, $vv_1$都不是 $T_n$悬挂边时, $u_1$的关联边和 $v_1$的关联边必全是正边, 这样圈 $C$上以 $v$为中心就有连续的4条正边 $v_2v_1$, $v_1v$, $vu_1$, $u_1u_2$.不妨
| $
C=K_1v_kv_{k-1}\cdots v_2v_1vu_1u_2\cdots u_lK_1.
$ |
当 $v_kK_1$为负边时, 同上面一样可知 $v_kv_{k-1}$必为正边, $v_{k-1}v_{k-2}$也必为正边.这时路 $v_kv_{k-1}\cdots v_2v_1v$上至多有 $\lfloor \frac{k-3}{2}\rfloor$条负边, 所以圈 $C$上路 $vv_1v_2\cdots v_k$的权 $\geq k-2\lfloor \frac{k-3}{2}\rfloor \geq 3$.
当 $v_kK_1$为正边时, 路 $vv_1v_2\cdots v_k$上至多有 $\lfloor \frac{k-1}{2}\rfloor$条负边, 所以圈 $C$上路 $vv_1v_2\cdots v_k$的权 $\geq k-2\lfloor \frac{k-1}{2}\rfloor \geq 1$.所以
若 $v_kK_1$为正边, $u_lK_1$为正边, 则 $f_1(C)\geq 1+1+1+1-2=2$.
若 $v_kK_1$为正边, $u_lK_1$为负边, 则 $f_1(C)\geq 1+3+1-1-2=2$.
若 $v_kK_1$为负边, $u_lK_1$为负边, 则 $f_1(C)\geq 3+3-1-1-2=2$.
所以 $f_1$是 $T_n+K_1$的一个强符号圈控制函数且 $f_1(E)=f(E)$.
若 $E(K_1)$中还有负边, 用上面同样的方法可以把这条负边改为正边, 得到 $T_n+K_1$的一个强符号圈控制函数 $f_2$使 $f_2(E)=f(E)$, $\cdots \cdots$, 一直这样下去, 最后必得 $T_n+K_1$的一个强符号圈控制函数 $f_t$使 $f_t(E)=f(E)$, 且在 $f_t$下 $E(K_1)$中的边全为正边.这时
| $
f(E)=f_t(E)=n-1+n-2|A|\geq 2n-1-2\alpha^\prime(T_n),
$ |
再结合(5) 式知 $\gamma_{ssc}^\prime(T_n+K_1)=2n-1-2\alpha^\prime(T_n)$.定理证毕.
定理2.4 $W_n$表示有 $n+1$个顶点的轮图, 则当 $n$是偶数时, $\gamma_{ssc}^\prime(W_n)=n+2$, 当 $n$是奇数时, $\gamma_{ssc}^\prime(W_n)=n+1$.
证 当 $n$偶数时, 不妨 $n\geq 6$. $W_n=C_n+v_0$, 用 $M$表示 $C_n$的一个最大匹配去掉一条边后得到的匹配.当 $e\in M$时, 令 $f(e)=-1$, 当 $e\notin M$时, 令 $f(e)=1$.则同定理2.3一样地可以证明 $f$是 $W_n$的一个强符号圈控制函数.所以
| $
\gamma_{ssc}^\prime(W_n)\leq f(E)=n+2.
$ |
(6) |
下面证明 $\gamma_{ssc}^\prime(W_n)\geq n+2$.
设 $f$是 $W_n$的任意一个强符号圈控制函数, $C_n=v_1v_2\cdots v_nv_1$, $W_n$的中心为 $v_0$.若 $E(v_0)$中有一条负边 $e_0=v_0v_1$, 则边 $v_0v_2, v_0v_3, v_0v_n, v_0v_{n-1}, v_1v_2, v_2v_3, v_1v_n, v_nv_{n-1}$都是正边.令 $e_0$取1, $v_1v_n$取 $-1$, 其他边的取值不变.
下面证明这样得到的函数 $g$仍是 $W_n$的一个强符号圈控制函数.这只要证明过 $v_1v_n$且不过 $v_0v_1$的圈 $C_1$的权都大于等于1即可.设圈 $C_1=v_nv_{n-1}\cdots v_{n-k}v_0v_lv_{l-1}\cdots v_1v_n$.当 $k=0$时, $v_0v_lv_{l-1}\cdots v_1v_0$是一个圈 $C_2$, 所以 $f(C_2)\geq 1$.路 $P_1=v_0v_lv_{l-1}\cdots v_1$, 则 $f(P_1)+f(v_1v_0)=f(C_2)\geq 1$, 所以 $f(P_1)\geq 1-f(v_1v_0)=2$.而 $f(P_1)=g(P_1)$, 故
| $
g(C_1)=g(v_nv_0)+g(P_1)+g(v_1v_n)\geq 1+2-1\geq
1.
$ |
当 $k>0$时, 路 $P_1=v_nv_{n-1}\cdots v_{n-k}v_0$, 路 $P_2=v_0v_lv_{l-1}\cdots v_1$, 因 $P_1v_0v_n$是圈, $P_2v_1v_0$是圈, 所以 $f(P_1)+f(v_0v_n)\geq 1$, $f(P_2)+f(v_1v_0)\geq 1$, 所以 $f(P_1)+1\geq 1$, $f(P_2)-1\geq 1$.显然 $g(P_1)=f(P_1), ~g(P_2)=f(P_2)$, 所以 $g(C_1)=g(P_1)+g(P_2)+g(v_1v_n)\geq 0+2-1=1$.又因为 $f(v_{n-1}v_{n-2}\cdots v_3v_0v_{n-1})\geq 1$, 所以
| $
f(v_{n-1}v_{n-2}\cdots v_3)=f(v_{n-1}v_{n-2}\cdots v_3v_0v_{n-1})-2\geq -1.
$ |
所以
| $
\begin{eqnarray*}
g(C_n)&=&g(v_{n-1}v_{n-2}\cdots v_3v_2v_1v_nv_{n-1})\\
&=&g(v_{n-1}v_{n-2}\cdots
v_3)+g(v_3v_2)+g(v_2v_1)+g(v_1v_n)+g(v_nv_{n-1})\\
&=&f(v_{n-1}v_{n-2}\cdots v_3)+1+1-1+1\geq
-1+1+1-1+1=1.\end{eqnarray*}
$ |
这样就证明了 $g$也是 $W_n$的一个强符号圈控制函数且 $g(W_n)=f(W_n)$.显然在 $g$下 $E(v_0)$中的负边条数比在 $f$下 $E(v_0)$中的负边条数少1.一直这样下去, 最后就能得到 $W_n$的一个强符号圈控制函数 $g$, 使 $E(v_0)$中的边全取1且 $g(W_n)=f(W_n)$.注意到 $C_n$中的负边不能邻接, 所以 $C_n$中的负边构成 $C_n$的一个匹配 $M_1$, 所以 $|M_1|\leq \frac{n}{2}-1$.据此得到 $f(W_n)=g(W_n)=n+n-2|M_1|\geq 2n-2(\frac{n}{2}-1)=n+2$.再结合(6) 式可知, $\gamma_{ssc}^\prime(W_n)=n+2$.同理可证当 $n$为奇数时, $\gamma_{ssc}^\prime(W_n)=n+1$.定理证毕.
2016, Vol. 36 
PDF