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

设$G=(V, E)$是一个图, 其顶点集$V=V(G)$和边集$E=E(G)$.对任意$u\in V(G)$, 则$N_{G}(u)$为$u$点在$G$中的领域, $N_{G}[u]=N_{G}(u)\cup \{u\}$为$u$点在$G$中的闭领域, $d_{G}(u)=|N_{G}(v)|$为$u$点在$G$中的度, 而$\delta=\delta(G)$和$\Delta=\Delta(G)$分别为图$G$的最小度和最大度.在不致混淆情况下, 可将$N_{G}(v), N_{G}[v], \Delta(G), \delta(G)$分别简单记为$N(v), N[v], \Delta, \delta$.用$C_{n}, P_{n}, F_{n}, W_{n}$分别表示$n$阶圈、路、扇图和轮图, 其中扇图$F_{m+1}$是指$m+1$个顶点的图, 即由一个中心顶点$w$连接$m$个顶点路$P_{m}$的所有顶点的图.轮图$W_{m+1}$是指$m+1$个顶点的图, 即由一个中心顶点$w$连接$m$个顶点圈$C_{m}$的所有顶点的图.图$n\cdot F_{m+1}$表示把$n$个扇图的中心点粘接而得到的图, 图$n\cdot W_{m+1}$表示把$n$个轮图的中心点粘接而得到的图.

近几十年来, 图的控制理论的研究内容越来越丰富, 各种类型的符号控制数以及其变化的形式依次被提出, 如图的符号控制数^[2-4]、图的边符号控制数^[5]、图的边全符号控制数^[5]、图的符号全控制数^[6]、图的星符号控制数^[5]、图的圈符号(边)控制数^[7]、图的团符号(边)控制数^[5]、图的逆符号(边)控制数^[5]、图的反符号(边)控制数^[5]、罗曼符号(边)控制数^{[8, 9]}等.其中首次被提出的是图的符号控制概念, 由Dunbar等人在1995年提出.图的符号控制数的研究有着广泛的应用背景, 如交通岗位、物资供应点的设置等, 但是符号控制数的计算是NP完全问题.

目前很多相关学者研究了关于图的符号全控制数的上下界^{[10, 11]}以及特殊图的符号全控制数的精确值^[12].文献[13]中, 吕新忠等人确定了完全图、星图、扇图、轮图以及完全多部图的符号全控制数.本文中主要得到了两类特殊图$n\cdot F_{m+1}$和$ n\cdot W_{m+1}$的符号全控制数的精确值.特别地, 当$n=1$时, 得到了扇图和轮图的符号全控制数, 从而改正了文献[13]中的两个关于扇图和轮图的符号全控制数的结果.

对于图$G=(V, E)$, 定义一个函数$f:V\mapsto R$和$G$的一个子集$S\subseteq V(G)$, 记$f(S)=\sum\limits_{v\in S}f(v)$.为简单起见, 下文中适合$f(u)=+1$的顶点称为+1点, 适合$f(u)=-1$的顶点称为$-1$点.

定义2.1   (文献[6])设图$G=(V, E)$为一个图, 一个双值函数$f: V\mapsto \{1, -1\}$, 如果对任意的顶点$v\in V$, 均有$f(N(v))\geq 1$成立, 则称$f$为图$G$的一个符号全控制函数, 图$G$的符号全控制数定义为$\gamma_{st}(G)=\text {min}\{f(V)| f$是图$G$的一个符号全控制函数$\}$, 并将使得$\gamma_{st}(G)=f(V)$的符号全控制函数称$f$为图$G$的一个最小符号全控制函数.

从符号全控制的定义, 容易看出以下结论.

引理2.2  设函数$f$是图$G$的符号全控制函数.对于$u\in V(G)$, 若$d(u)\equiv 0 (\text {mod} 2)$, 则$f(N(u))$为偶数.若$d(u)\equiv 1 (\text {mod} 2)$, 则$f(N(u))$为奇数.

定理3.1  若$n\geq 1, m> 1$, 则

$ {\gamma _{st}}(n \cdot {F_{m + 1}}) = \left\{ {\begin{array}{*{20}{c}} {2n + 1, 当m \equiv {\rm{2}}({\rm{mod4}}), }\\ {3, \;\;\;\;\;\;当m \equiv {\rm{0}}({\rm{mod4}}), }\\ {n + 1, 当m \equiv {\rm{1}}({\rm{mod2}});} \end{array}} \right. $

若$n\geq 1, m=1$, 则

$ \begin{array}{l} \\ {\gamma _{st}}(n \cdot {F_{m + 1}}) = \left\{ {\begin{array}{*{20}{c}} {2, \;\;\;当n \equiv {\rm{1}}({\rm{mod2}}), }\\ {3, \;\;\;当n \equiv {\rm{0}}({\rm{mod2}}), } \end{array}} \right. \end{array} $

证  令图$n\cdot F_{m+1}$是由$n$个扇图$F_{m+1}$的中心点粘接而得到的图, 记为

$ n\cdot F_{m+1}=F_{m+1}^{(1)}\cup F_{m+1}^{(2)}\cup \cdots \cup F_{m+1}^{(n)}, $

其中$F_{m+1}^{(i)}$是由中心点$w$与路$P^{(i)}=u_{1}^{(i)}, u_{2}^{(i)}, \cdots, u_{m}^{(i)}$上每个顶点相连接而得到的图.记

$ \begin {eqnarray*} V(F_{m+1}^{(i)})&=&\{w, u_{1}^{(i)}, u_{2}^{(i)}, \cdots , u_{m}^{(i)}\}, 1\leq i\leq n, \\ E(F_{m+1}^{(i)})&=&\{wu_{j}^{(i)}|1\leq j \leq m\}\cup \{u_{j}^{(i)}u_{j+1}^{(i)}|1\leq j \leq m-1\}, 1\leq i \leq n. \end {eqnarray*} $

首先证明

$ \gamma_{st}(n\cdot F_{m+1})\geq \left\{\begin{array}{ll} 2n+1, \;\;\;{当 m\equiv 2(\rm{mod 4})}, \\ 3, \;\;\;{当 m\equiv 0(\rm{mod 4})}, \\ n+1, \;\;\;{当 m\equiv 1(\rm{mod 2})}.\\ \end{array}\right. $

令$f$是图$n\cdot F_{m+1}$的一个最小符号全控制函数, 则$f(V(G))=\gamma_{st}(n\cdot F_{m+1})$.

设图$n\cdot F_{m+1}$中所有$-1$点个数为$t$, 所有+1点个数为$s$, 则有$s+t=nm+1$, 从而有

$ \gamma_{st}(n\cdot F_{m+1})=nm+1-2t. $

因为$f(N(u_{1}^{(i)}))=f(w)+f(u_{2}^{(i)})\geq 1$, 故$f(w)=f(u_{2}^{(i)})=+1, i=1, \cdots, n.$

当$m=1$时, 图$n\cdot F_{m+1}$是$n+1$个顶点的星图$K_{1.n}=\{w, u_{1}^{(1)}, \cdots , u_{1}^{(n)}\}$, 此时给出星图的符号全控制函数$f$如下: $f(w)=+1, $

$ f(u_{1}^{(i)})= \left\{\begin{array}{ll} +1, \;\;\;{当 i=1, \cdots , \lceil\frac{n}{2}\rceil }, \\ -1, \;\;\;{当 i=\lceil\frac{n}{2}\rceil+1, \cdots, n}.\\ \end{array}\right. $

容易验证, 此时函数$f$为最优, 从而有

$ \gamma_{st}(n\cdot F_{m+1})= \left\{\begin{array}{ll} 2, \;\;\;{当 n\equiv 1(\rm{mod 2})}, \\ 3, \;\;\;{当 n\equiv 0(\rm{mod 2})}.\\ \end{array}\right. $

当$m=2$时, 图$n\cdot F_{m+1}$中每个顶点必标为+1, 从而有$\gamma_{st}(n\cdot F_{m+1})=2n+1.$

下面只考虑当$m\geq 3$.为此通过分三种情况来证明图$n\cdot F_{m+1}$的符号全控制数的下界.

情况1  当$m\equiv 0 (\text {mod} 4)$时, 因$d(w)\equiv 0 (\text {mod} 2)$, 由引理知, $f(N(w))$为偶数, 从而有

$ f(N(w))\geq 2. $

故

$ \gamma_{st}(n\cdot F_{m+1})=f(V)=f(N(w))+f(w) \geq 3. $

情况2  当$m\equiv2 (\text {mod} 4)$时, 先证明以下五个断言(这里$1\leq i \leq n$).

断言1  每条路$P^{(i)}$上没有连续三个标为$-1$的点.否则, 不妨设$f(u_{j-1}^{(i)})=f(u_{j}^{(i)})=f(u_{j+1}^{(i)})=-1$, 那么对于点$u_{j}^{(i)}$, 有

$ f(N(u_{j}^{(i)}))=f(w)+f(u_{j-1}^{(i)})+f(u_{j+1}^{(i)})=-1, $

这与符号全控制函数的定义矛盾.

断言2  若$U=\{u_{r}^{(i)}, u_{s}^{(i)}|f(u_{r}^{(i)})=f(u_{s}^{(i)})=-1, d(u_{r}^{(i)}, u_{s}^{(i)})=2\}\subseteq V(P^{(i)})$, 则$U=\emptyset$.否则, 存在两个顶点$u_{r}^{(i)}, u_{r+2}^{(i)}$使得$f(u_{r}^{(i)})=f(u_{r+2}^{(i)})=-1$且$d(u_{r}^{(i)}, u_{r+2}^{(i)})=2$, 那么对于顶点$u_{r+1}^{(i)}$, 有

$ f(N(u_{r+1}^{(i)}))=f(w)+f(u_{r}^{(i)})+f(u_{r+2}^{(i)})=-1 $

这与符号全控制函数的定义矛盾.

结合断言1和断言2, 推出下面的断言3和断言4.

断言3  每条路$P^{(i)}$上连续三个顶点中至多有两个顶点标为$-1$.

断言4  每条路$P^{(i)}$上连续四个顶点中至多有两个顶点标为$-1$.

断言5  每条路$P^{(i)}$上顶点中至多有$\frac{m}{2}-1$个标为$-1$的点.

因为$f(u_{2}^{(i)})=f(u_{m-1}^{(i)})=1$, 由$f(N(u_{2}^{(i)}))=f(u_{1}^{(i)})+f(w)+f(u_{3}^{(i)})\geq 1$, 有$f(u_{1}^{(i)})+f(u_{3}^{(i)})\geq 0$.同理, 有$f(u_{m}^{(i)})+f(u_{m-2}^{(i)})\geq 0$, 故$f(u_{1}^{(i)})$, $f(u_{2}^{(i)})$, $f(u_{3}^{(i)})$中至多有一个$-1$点.从而在$f(u_{m}^{(i)})$, $f(u_{m-1}^{(i)})$, $f(u_{m-2}^{(i)})$中也至多有一个$-1$点.剩余顶点个数为$m-6$个, 再由断言3可知在剩余顶点中至多有$\frac{m-6}{2}$个$-1$点.故$P^{(i)}$上顶点中至多有2+$\frac{m-6}{2}$=$\frac{m}{2}-1$个$-1$点.

因为$\gamma_{st}(n\cdot F_{m+1})=nm+1-2t$.由断言5可知

$ \gamma_{st}(n\cdot F_{m+1})=nm+1-2t\geq nm+1-2n(\frac{m}{2}-1)=2n+1. $

情况3  当$m\equiv1 (\text {mod} 2)$时, 情况2中的断言1、2、3、4依然成立.

断言6  每条路$P^{(i)}$上顶点中至多有$\frac{m-1}{2}$个标为$-1$的点.

当$m=3$时, 由于$f(u_{2}^{(i)})=1$且$f(u_{1}^{(i)}), f(u_{3}^{(i)})$不能同时为$-1$, 从而每条路$P^{(i)}$上顶点中至多有$1$个标为$-1$点.当$m=5$时, 由于$f(u_{2}^{(i)})=f(u_{4}^{(i)})=1$且$f(u_{1}^{(i)}), f(u_{3}^{(i)}), f(u_{5}^{(i)})$不能同时为$-1$, 从而每条路$P^{(i)}$上顶点中至多有$2$个标为$-1$点.当$m\geq 7$时, 因为$f(u_{2}^{(i)})=f(u_{m-1}^{(i)})=1$且$f(N(u_{2}^{(i)}))\geq 1$, $f(N(u_{m-1}^{(i)}))\geq 1$, 故$f(u_{1}^{(i)})$, $f(u_{2}^{(i)})$, $f(u_{3}^{(i)})$中至多有一个$-1$点.同理有$f(u_{m}^{(i)})$, $f(u_{m-1}^{(i)})$, $f(u_{m-2}^{(i)})$中至多有一个$-1$点.再由断言3、4可知, 剩余$m-6$个点中至多有$\frac{m-5}{2}$个$-1$点, 故路$P^{(i)}$上至多有$2+\frac{m-5}{2}=\frac{m-1}{2}$个$-1$点.

从断言6可知, $n\cdot F_{m+1}$中所有$-1$点个数$t$至多为$n(\frac{m-1}{2})$个, 从而有

$ \begin{eqnarray*} \gamma_{st}(n\cdot F_{m+1})&=&nm+1-2t \geq nm+1-2n(\frac{m-1}{2})\\ &=&nm+1-n(m-1) =n+1. \end{eqnarray*} $

综上所述, 有

$ \gamma_{st}(n\cdot F_{m+1})\geq \left\{\begin{array}{ll} 2n+1, \;\;\;{当 m\equiv 2(\rm{mod 4})}, \\ 3, \;\;\;{当 m\equiv 0(\rm{mod 4})}, \\ n+1, \;\;\;{当 m\equiv 1(\rm{mod 2})}.\\ \end{array}\right. $

下面给出$n\cdot F_{m+1}$的符号全控制的上界.

情况1  当$m\equiv0 (mod 4)$时, 给出$n\cdot F_{m+1}$的一个符号全控制函数$f$: $f(w)=+1.$

当$m=4$时, 令

$ f(u_{j}^{(i)})= \left\{\begin{array}{ll} +1, \;\;\;{当 i=1, j\neq 1 }, \\ \;\;\;\;\;\;{当 i\neq 1, j=2, 3 };\\ -1, \;\;{当 i=1, j=1}, \\ \;\;\;\;\;\;{当 i\neq 1, j=1, 4}.\\ \end{array}\right. $

当$m> 4$时, 令

$ f(u_{j}^{(i)})= \left\{\begin{array}{ll} +1, \;\;{当 i=1, 2, 3, \cdots , n, j=2, 3, m-1, m-2 }, \\ \;\;\;\;\;\;\;{当 i\neq 1, 4\leq j \leq m-3 且 j \equiv 2 , 3(\rm{mod 4}) }, \\ \;\;\;\;\;\;\;{当 i=1, 4\leq j \leq m-4 且 j \equiv 2 , 3(\rm{mod 4}), j=m-3 };\\ -1, \;\;{当 i=1, 2, 3, \cdots , n, j=1, m}, \\ \;\;\;\;\;\;\;{当 i\neq 1, 4\leq j \leq m-3 且 j \equiv 0 , 1(\rm{mod 4})}, \\ \;\;\;\;\;\;\;{当 i=1, 4\leq j \leq m-4 且 j \equiv 0 , 1(\rm{mod 4})}.\\ \end{array}\right. $

容易验证, 此时$f(V)=3$, 从而有

$ \gamma_{st}(n\cdot F_{m+1})\leq 3 $

情况2  当$m\equiv 2 (\text {mod} 4)$时, 对于$1\leq i \leq n$, 给出$n\cdot F_{m+1}$的一个符号全控制函数$f$: $f(w)=+1, $

$ f(u_{j}^{(i)})= \left\{\begin{array}{ll} +1, \;\;{当 j=2, 3, m-1, m-2 }, \\ \;\;\;\;\;\;{当 4\leq j \leq m-3 , j \equiv 2 , 3(\rm{mod 4}) };\\ -1, \;\;{当 j=1, m }, \\ \;\;\;\;\;\;{当 4\leq j \leq m-3 , j \equiv 0 , 1(\rm{mod 4}) }.\\ \end{array}\right. $

容易验证, 此时$f(V)=2n+1$, 从而有$\gamma_{st}(n\cdot F_{m+1})\leq 2n+1$.

情况3  当$m\equiv1 (\text {mod} 2)$时, 对于$1\leq i \leq n$, 给出$n\cdot F_{m+1}$的一个符号全控制函数$f$: $f(w)=+1$.

当$m=3$时, 令

$ f(u_{j}^{(i)})= \left\{\begin{array}{ll} +1, \;\;\;{当 j=2, 3 }, \\ -1, \;\;\;{当 j=1 }.\\ \end{array}\right. $

当$m=5$时, 令

$ f(u_{j}^{(i)})= \left\{\begin{array}{ll} +1, \;\;\;{当 j=2, 3, 4 }, \\ -1, \;\;\;{当 j=1, 5 }.\\ \end{array}\right. $

当$m> 5$时, 令

$ f(u_{j}^{(i)})= \left\{\begin{array}{ll} +1, \;\;\;{当 j=2, 3, m-1, m-2 }, \\ \;\;\;\;\;\;{当 4\leq j \leq m-3 , j \equiv 2 , 3(mod~4) };\\ -1, \;\;\;{当 j=1, m }, \\ \;\;\;\;\;\;{当 4\leq j \leq m-3 , j \equiv 0 , 1(mod~4) }.\\ \end{array}\right. $

容易验证, 此时$f(V)=n+1$, 从而有

$ \gamma_{st}(n\cdot F_{m+1})\leq n+1 $

综上所述, 有

$ \gamma_{st}(n\cdot F_{m+1})\leq \left\{\begin{array}{ll} 2n+1, \;\;\;{当 m\equiv 2(\rm{mod 4})}\\ 3, \;\;\;\;\;\;{当 m\equiv 0(\rm{mod 4})}\\ n+1, \;\;\;{当 m\equiv 1(\rm{mod 2})}\\ \end{array}\right. $

定理1证毕.

注  定理1中当$m=1$时, 得到了$n+1$阶星图的符号全控制数的结果, 这与文^[13]中的结论一致.

定理3.2  设$n\geq 1, m\geq 3$, 则

$ \gamma_{st}(n\cdot W_{m+1})= \left\{\begin{array}{ll} 2n+1, \;\;\;{当 m\equiv 2(\rm{mod 4})}\\ 3, \;\;\;\;\;\;{当 m\equiv 0(\rm{mod 4})}\\ n+1, \;\;\;{当 m\equiv 1(\rm{mod 2})}\\ \end{array}\right. $

证  令图$n\cdot W_{m+1}$是由$n$个轮图$W_{m+1}$的中心点粘接而得到的图, 记为

$ n\cdot W_{m+1}=W_{m+1}^{(1)}\cup W_{m+1}^{(2)}\cup \cdots \cup W_{m+1}^{(n)} $

其中$W_{m+1}^{(i)}$是由中心点$w$与圈$C^{(i)}=u_{1}^{(i)}, u_{2}^{(i)}, \cdots, u_{m}^{(i)}, u_{1}^{(i)}$上每个顶点相连接而得到的图.记

$ \begin{eqnarray*} V(W_{m+1}^{(i)})&=&\{w, u_{1}^{(i)}, u_{2}^{(i)}, \cdots , u_{m}^{(i)}\}, 1\leq i\leq n, \\ E(W_{m+1}^{(i)})&=&\{wu_{j}^{(i)}|1\leq j \leq m\}\cup \{u_{j}^{(i)}u_{j+1}^{(i)}|1\leq j \leq m-1\}\cup \{u_{1}^{(i)}u_{m}^{(i)}\}, 1\leq i \leq n. \end{eqnarray*} $

令$f$是图$n\cdot W_{m+1}$的一个最小符号全控制函数, 则

$ f(V(G))=\gamma_{st}(n\cdot W_{m+1}). $

设$n\cdot W_{m+1}$中所有$-1$点个数为$t$, 所有+1点个数为$s$, 则有$s+t=nm+1, $从而有

$ \gamma_{st}(n\cdot W_{m+1})=nm+1-2t. $

首先证明

$ \gamma_{st}(n\cdot W_{m+1})\geq \left\{\begin{array}{ll} 2n+1, \;\;\;{当 m\equiv 2(\rm{mod 4})}\\ 3, \;\;\;\;\;\;{当 m\equiv 0(\rm{mod 4})}\\ n+1, \;\;\;{当 m\equiv 1(\rm{mod 2})}\\ \end{array}\right. $

若$f(w)=-1$时, 注意到, 对于每个点$u_{j}^{(i)}$有$f(N(u_{j}^{(i)}))\geq 1$且$w\in N(u_{j}^{(i)})$, 从而必有$f(u_{j}^{(i)})= 1$.故, 有

$ \gamma_{st}(n\cdot W_{m+1})=mn-1. $

若$f(w)=1$时, 分情况讨论图$n\cdot W_{m+1}$的符号全控制数的下界.

情况1  当$m\equiv 0 (\text {mod} 4)$时, 同证明定理1中的下界时的情况1一样推导出

$ \gamma_{st}(n\cdot W_{m+1})=f(V)=f(N(w))+f(w) \geq 3. $

情况2  当$m\equiv2 (\text {mod} 4)$时, 定理1中的断言1、2、3、4仍然成立.

断言7  每个圈$C^{(i)}$上顶点中至多有$\frac{m}{2}-1$个标为$-1$的点.因为$f(N(u_{1}^{(i)}))=f(u_{2}^{(i)})+f(w)+f(u_{m}^{(i)})\geq 1$, 有$f(u_{2}^{(i)})+f(u_{m}^{(i)})\geq 0$.同理, 有

$ f(u_{1}^{(i)})+f(u_{m-1}^{(i)})\geq 0. $

故$\{f(u_{1}^{(i)}), f(u_{2}^{(i)}), f(u_{m}^{(i)}), f(u_{m-1}^{(i)})\} $中至多有两个$-1$点.剩余顶点个数为$m-4$个, 其中顶点$\{f(u_{3}^{(i)}), \cdots , f(u_{m-4}^{(i)})\}$中, 由断言4可知至多有$\frac{m-6}{2}$个$-1$点.从而剩余两个顶点$f(u_{m-2}^{(i)})=f(u_{m-3}^{(i)})=+1$(否则, 存在一个点$u_{j}^{(i)}\in V(C^{(i)})$使得$f(N(u_{j}^{(i)}))< 1$, 这与符号全控制数的定义矛盾).故$C^{(i)}$上顶点中至多有2+$\frac{m-6}{2}$=$\frac{m}{2}-1$个$-1$点.

因为$\gamma_{st}(n\cdot W_{m+1})=nm+1-2t$.由断言7可知

$ \gamma_{st}(n\cdot W_{m+1})=nm+1-2t\geq nm+1-2n(\frac{m}{2}-1)=2n+1. $

情况3  当$m\equiv1 (\text {mod} 2)$时, 定理1中的断言1、2、3、4仍然成立.

断言8  每圈$C^{(i)}$上顶点中至多有$\frac{m-1}{2}$个标为$-1$的点.

从上述情况2知, $\{f(u_{1}^{(i)}), f(u_{2}^{(i)}), f(u_{m}^{(i)}), f(u_{m-1}^{(i)})\} $中至多有两个$-1$点.剩余顶点个数为$m-4$个, 其中顶点$\{f(u_{3}^{(i)}), \cdots , f(u_{m-3}^{(i)})\}$中, 由断言4可知至多有$\frac{m-5}{2}$个$-1$点.从而剩余一个顶点$f(u_{m-2}^{(i)})=+1$(否则, 存在一个点$u_{j}^{(i)}\in V(C^{(i)})$使得$f(N(u_{j}^{(i)}))< 1$, 这与符号全控制数的定义矛盾).故, 圈$C^{(i)}$上至多有$2+\frac{m-5}{2}=\frac{m-1}{2}$个$-1$点.

从断言8可知, $n\cdot W_{m+1}$中所有$-1$点个数$t$至多为$n(\frac{m-1}{2})$个, 从而有

$ \begin{eqnarray*} \gamma_{st}(n\cdot W_{m+1})&=&nm+1-2t \geq nm+1-2n(\frac{m-1}{2})\\ &=&nm+1-n(m-1) =n+1. \end{eqnarray*} $

考虑到当$f(w)=-1$和$f(w)=1$时的图$n\cdot W_{m+1}$的符号全控制数的下界, 容易得出

$ \gamma_{st}(n\cdot W_{m+1})\geq \left\{\begin{array}{ll} 2n+1, \;\;\;{当 m\equiv 2(\rm{mod 4})}, \\ 3, \;\;\;\;\;\;{当 m\equiv 0(\rm{mod 4})}, \\ n+1, \;\;\;{当 m\equiv 1(\rm{mod 2})}.\\ \end{array}\right. $

下面再考虑图$n\cdot W_{m+1}$的符号全控制的上界.同定理1的证明, 现只需定义一个符号全控制数函数$g$使得$g=f$ (这里$f$是指定理1情况3中给出的函数$f$).

因图$n\cdot W_{m+1}$比图$n\cdot F_{m+1}$多了边$\{u_{1}^{(i)}u_{m}^{(i)}\}$, 增加此边时只有对两个端点$u_{1}^{(i)}$, $u_{m}^{(i)}$的符号全控制数有变化.事实上, 在符号全控制数函数$g$下, 有$g(N(u_{1}^{(i)}))=1, g(N(u_{m}^{(i)}))=1$.对于顶点$u\neq u_{1}^{(i)}, u_{m}^{(i)}$, 有$g(N(u))=f(N(u))$.容易验证, 得出

$ \gamma_{st}(n\cdot W_{m+1})\geq \left\{\begin{array}{ll} 2n+1, \;\;\;{当 m\equiv 2(\rm{mod 4})}, \\ 3, \;\;\;\;\;\;{当 m\equiv 0(\rm{mod 4})}, \\ n+1, \;\;\;{当 m\equiv 1(\rm{mod 2})}.\\ \end{array}\right. $

证毕.

特别地, 定理1和定理2中当$n=1$时, 分别得到扇图和轮图的符号全控制数的结果.

推论3.3  若$n=1, m\geq 1$, 则

$ \gamma_{st}(F_{m+1})= \left\{\begin{array}{ll} 3, \;\;\;{当 m\equiv 0(\rm{mod 2})}, \\ 2, \;\;\;{当 m\equiv 1(\rm{mod 2})}.\\ \end{array}\right. $

若$n=1, m\geq 2$, 则

$ \gamma_{st}(W_{m+1})= \left\{\begin{array}{ll} 3, \;\;\;{当 m\equiv 0(\rm{mod 2})}, \\ 2, \;\;\;{当 m\equiv 1(\rm{mod 2})}.\\ \end{array}\right. $

注  事实上, 定理1证明过程中的断言3否定了文^[13]中的证明过程, 从而得出扇图和轮图的符号全控制数的精确值.