本文考虑的图均指连通有限无向简单图. 对于给定的图$ G=(V, E) $, 任意$ x\in E(G) $(或$ x\in V(G)) $, $ {N}_{G}(x) $表示$ x $的开邻域, $ {N}_{G}[x]={N}_{G}(x)\cup \{x\} $表示$ x $的闭邻域. 设$ X $为$ E(G) $ (或$ V(G) $)的非空真子集, $ G[X] $表示$ X $的导出子图, $ E(G)-X $ (或$ V(G)-X $)的导出子图简记为$ G-X $.

设$ G $和$ H $是两个简单无向图, $ G\cong H $表示$ G $和$ H $同构, $ G\times H $表示$ G $与$ H $的笛卡尔乘积图. $ n $阶路记作$ P_{n} $. 长为$ m $的圈称为$ m- $圈, 记为$ C_{m} $. $ \lfloor x \rfloor $和$ \lceil x\rceil $分别表示$ x $的下整数和上整数. 为了书写方便, 我们用$ \bigcup\limits_{i=1}^{n} V_{i} $表示$ {P_m}\times{P_n} $的顶点集, 其中$ V_{i} = \left \{ v_{1}^{i}, v_{2}^{i}, \dots , v_{m}^{i} \right \}, \; 1\le i\le n, $它的边集为

$ \left \{v _{j}^{i}v _{j}^{i+1} \mid 1\le j\le m;1\le i\le n-1 \right \} \cup \left \{v _{j}^{i}v _{j+1}^{i} \mid 1\le j\le m-1;1\le i\le n \right \}. $

$ 2001 $年徐保根^[1]定义符号边控制函数和符号边控制数, 并获得了符号边控制数的许多界.

定义1.1^[1]  设$ G=(V, E) $为非空简单图, 如果存在一个函数$ f:E\rightarrow \{-1, +1\} $使得对每一条边$ e\in E $的闭邻域$ {N_G}[e] $, 满足

$ \sum\limits_{e^{'}\in {N_G}[e]}f(e^{'})\geq1, $

则称$ f $是图$ G $的一个符号边控制函数.

为方便起见, 记$ f(S)=\sum\limits_{e\in S}f(e), \; (S\subseteq E) $; $ S_f=\mid\{e\in E(G)\mid f(e)=-1\}\mid. $

定义1.2^[1]  称$ {\gamma}_{s}^{'}(G)=\min\{f(E)|f $是$ G $的符号边控制函数$ \} $为$ G $的符号边控制数. $ f(E)={\gamma}_{s}^{'}(G) $的$ G $的符号边控制函数$ f $称为$ G $的最小符号边控制函数.

之后, 国内外研究学者对符号边控制问题进行了深入研究, 目前对于图的符号边控制数的上下界的精确估计仍是人们比较感兴趣的问题, 其结果也越来越丰富, 如徐保根在[2]中研究了几种类型的边控制问题并且得到了相关的问题和猜想, 在[3]中给出了一类偶图的符号边控制数, 在[4]中给出了图$ G $的符号边控制数的一个下界, 同时确定了圈、路、完全图的符号边控制数; 汤青芽, 李向军^[5]给出了笛卡尔乘积图$ P_{3}\times C_{n} $的符号边控制数; 李向军, 袁旭东^[6]给出了$ C_{3}\times C_{n} $的符号边控制数. 本文将对$ P_m\times P_n $ $ (m=2, 3, 4) $的符号边控制进行研究, 并确定其符号边控制数.

定理2.1  设$ G={P_2}\times{P_n}\left ( n\ge 2\right ) $, 则$ {\gamma}_{s}^{'}(G)= n . $

证  定义图$ G $的一个$ E\left ( G \right ) $到$ \{-1, +1\} $的函数$ g $如下:

$ \begin{equation*} g\left ( e\right ) =\begin{cases} -1, & e=v_1^iv_1^{i+1}, i\equiv 1\left ( \text{mod}\; 2 \right )\text{且}\; 1\le i\le n-1;\\ -1, & e=v_2^iv_2^{i+1}, i\equiv 0\left ( \text{mod}\; 2 \right )\text{且}\; 2\le i\le n-1;\\ 1, & \text{其他.} \end{cases} \end{equation*} $

易验证$ g $是$ G $的符号边控制函数, 且$ {\gamma}_{s}^{'}(G)\leq g(E(G))= 3n-2-2(n-1)=n. $

下面证$ {\gamma}_{s}^{'}(G)\ge n $. 设$ f $是$ G $的最小符号边控制函数, 只需证$ S_f\leq n-1 $. 对$ n $应用数学归纳法. 当$ n=2 $时, 易验证$ S_{f}=1 $, 结论成立. 假设结论对小于$ n $大于$ 1 $的自然数都成立, 下证对$ n $也成立. 若$ E(G) $中有两条相邻的边在$ f $下值均为$ -1 $, 由$ G $的对称性, 不妨设存在$ i $, 使得$ f\left ( v_{1}^{i}v_{1}^{i+1} \right ) =f\left ( v_{1}^{i+1}v_{k}^{t} \right ) =-1 $, 这里$ k=1, t=i+2 $或者$ k=2, t=i+1 $, 则由符号边控制函数的定义知$ 2\le i\le n-3 $, 且$ f\left ( v_{2}^{i}v_{2}^{i+1} \right ) =f\left ( v_{2}^{i+1}v_{2}^{i+2} \right )=1 $. 在$ { v_{1}^{i+1}v_{2}^{i+1} } $处把$ {P_2}\times{P_n} $分成两部分$ G_{1} $和$ G_{2} $, 即$ G_{1}\cup G_{2}={P_2}\times{P_n}, G_{1}\cap G_{2}=G\left [ \left\{ v_{1}^{i+1}v_{2}^{i+1} \right\}\right ] $. 可验证$ f|_{G_2} $是$ G_2 $的符号边控制函数. 对$ G_1 $定义$ f^1:E(G_1)\rightarrow \{1, -1\} $如下:

$ f^1(e)=\left\{\begin{array}{ll} 1, & e=v_1^{i+1}v_2^{i+1} 且 f(e)=-1 ;\\ f(e), &\text{其他.}\end{array}\right. $

易验证$ f^1 $是$ G_1 $的符号边控制函数, 且$ S_f=S_{f^1}+S_{f|_{G_2}} $. 由$ G_{1 }\cong {P_2}\times{P_{n_1}} $, $ G_{2 }\cong {P_2}\times{P_{n_2}} $, $ n_{1 }=i+1\ge 3 $, $ n_{2 }=n-i\ge 3 $, 及归纳假设知, $ S_{f^1}\le n_{1}-1, S_{f\mid _{G_{2}}}\le n_{2}-1. $从而

$ S_{f}=S_{f^1}+S_{f\mid _{G_{2}}} \le (n_{1}-1)+(n_{2}-1) =(n_{1}+n_{2})-2 =n-1. $

下设值为$ -1 $的边两两不相邻, 即构成$ G $的一个匹配$ M $. 若$ v_{1}^{1}v_{2}^{1}\in M $, 则$ v_{1}^{2}v_{1}^{3}, v_{2}^{2}v_{2}^{3}, v_1^2v_2^2\notin M $; 若$ v_{1}^{1}v_{2}^{1}\notin M $, 则$ v_{1}^{1}v_{1}^{2} $和$ v_{2}^{1}v_{2}^{2} $至多有一条属于$ M $, 所以$ M $不是$ P_{2} \times P_{n} $的完美匹配, 因而$ |M|\le n-1 $, 从而$ S_{f}\le n-1. $

综上对$ n\ge 2 $有$ S_f\leq n-1 $, 从而结论成立.

定理2.2  设$ G={P_3}\times{P_n}\left ( n\ge 3\right ) $, 则$ {\gamma}_{s}^{'}(G)= 5n-3-2\left \lfloor \frac{3n+\left \lfloor \frac{n-1}{3} \right \rfloor-3}{2} \right \rfloor. $

证  定义图$ G $的一个$ E\left ( G \right ) $到$ \left \{ -1, 1 \right \} $的函数$ g $如下:

$ g\left ( e\right ) =\left\{\begin{array}{ll} -1, & e=v_{j}^{i} v_{j}^{i+1}, i\equiv 1\left ( \text{mod}\; 3 \right ) 且 i\ne n-1 或 i\equiv 0\left ( \text{mod}\; 3 \right ), j=1, 3 ;\\ -1, & e=v_{j}^{i} v_{j}^{i+1}, i\equiv 2\left ( \text{mod}\; 3 \right ) 或 i\equiv 1\left ( \text{mod}\; 3 \right ) 且 i= n-1, j=2 ;\\ 1, &\text{其他}. \end{array}\right. $

易验证$ g $是$ G $的符号边控制函数, 且$ {\gamma}_{s}^{'}(G)\leq g(E(G))= 5n-3-2\left \lfloor \frac{3n+\left \lfloor \frac{n-1}{3} \right \rfloor-3}{2} \right \rfloor. $

下面证$ {\gamma}_{s}^{'}(G)\ge 5n-3-2\left \lfloor \frac{3n+\left \lfloor \frac{n-1}{3} \right \rfloor-3}{2} \right \rfloor $. 设$ f $是$ G $的最小符号边控制函数, 只需证

$ S_f\leq \left \lfloor \frac{3n+\left \lfloor \frac{n-1}{3} \right \rfloor-3}{2} \right \rfloor. $

对$ n\geq 3 $应用数学归纳法. 当$ n=3 $时, $ {S}_{f}=3=\left \lfloor \frac{{3}\times{3}+\left \lfloor \frac{3-1}{3} \right \rfloor-3}{2} \right \rfloor $, 结论成立. 假设结论对于大于$ 2 $小于$ n $的整数成立, 下证结论对$ n $也成立. 由符号边控制函数的定义知, 与$ G $的第一列顶点关联的边中至多有两条在$ f $下值为$ -1 $, 且恰有两条值为$ -1 $时, $ f\left ( v_{1}^{1}v_{1}^{2} \right ) =f\left ( v_{3}^{1}v_{3}^{2} \right )=-1 $.

情形1  $ f\left ( v_{1}^{1}v_{1}^{2} \right )=-1 $或$ f\left ( v_{3}^{1}v_{3}^{2} \right )=-1 $. 不妨设为前者, 由符号边控制函数的定义知, $ f(v_1^2v_1^3)=1 $, 与$ v_3^2 $关联的边至多有一条边在$ f $下值为$ -1 $, 且$ f(v_1^3v_2^3) $与$ f(v_1^3v_1^4) $不同时为$ -1 $. 若$ f(v_2^2v_3^2)=-1 $或$ f(v_3^2v_3^3)=-1 $, 则交换$ v_3^1v_3^2 $与$ v_2^2v_3^2 $或$ v_3^2v_3^3 $的$ f $值得到的$ f' $仍然是$ G $的最小符号边控制函数. 因此不妨设$ f(v_2^2v_3^2)=f(v_3^2v_3^3)=1 $, 则与$ v_2^2 $关联的边只有$ v_2^2v_2^3 $在$ f $下的值可能为$ -1 $. 若$ f(v_2^2v_2^3)=-1 $, 则$ f(v_1^3v_2^3), f(v_2^3v_3^3) $, $ f(v_3^3v_3^4) $, $ f(v_2^3v_2^4) $至多有一个为$ -1 $. 令$ G_1 $和$ G_2 $分别是$ G $的前两列和后$ n-2 $列顶点导出的子图, 则$ f|_{G_1} $和$ f|_{G_2} $分别是$ G_1 $和$ G_2 $的符号边控制函数. 由$ G_1\cong P_3\times P_2 $, $ G_2\cong P_3\times P_{n-2} $, 定理1及归纳假设知

$ S_{f|_{G_1}}\leq 2, \; \; \; S_{f|_{G_2}}\leq \left \lfloor \frac{3(n-2)+\left \lfloor \frac{n-3}{3} \right \rfloor-3}{2} \right \rfloor. $

从而

$ S_f=S_{f|_{G_1}}+S_{f|_{G_2}}+1\leq \left \lfloor \frac{3n+\left \lfloor \frac{n-1}{3} \right \rfloor-3}{2} \right \rfloor. $

若$ f(v_2^2v_2^3)=1 $, 则由$ f $的最小性知, 与$ v_2^3 $关联的其他三条边中至少有一条$ e $在$ f $下值为$ -1 $, 交换$ v_2^2v_2^3 $与满足上述条件的一条边$ e $的$ f $值得到的$ f' $仍是$ G $的最小符号边控制函数且$ f'(v_2^2v_2^3)=-1 $, 由上面的证明知结论成立.

情形2  $ f\left ( v_{1}^{1}v_{2}^{1} \right )=-1 $或$ f\left ( v_{2}^{1}v_{3}^{1} \right )=-1 $或$ f\left ( v_{2}^{1}v_{2}^{2} \right )=-1 $. 对于前两种类型, 当$ f(v_2^2v_2^3)=-1 $时, 交换$ v_{1}^{1}v_{2}^{1} $和$ v_1^1v_1^2 $或$ v_{2}^{1}v_{3}^{1} $和$ v_3^1v_3^2 $的$ f $值得到$ f' $是$ G $的最小符号边控制函数, $ S_f=S_{f'} $且$ f'\left ( v_{1}^{1}v_{1}^{2} \right )=-1 $或$ f'\left ( v_{3}^{1}v_{3}^{2} \right )=-1 $, 由情形1知结论成立; 当$ f(v_2^2v_2^3)=1 $时, 交换$ v_{1}^{1}v_{2}^{1} $和$ v_2^1v_2^2 $或$ v_{2}^{1}v_{3}^{1} $和$ v_2^1v_2^2 $的$ f $值得到$ f' $是$ G $的最小符号边控制函数, $ S_f=S_{f'} $且$ f'\left ( v_{2}^{1}v_{2}^{2} \right )=-1 $. 因此不妨设$ f\left ( v_{2}^{1}v_{2}^{2} \right )=-1 $, 则$ f $限制在$ G $的后$ n-1 $列的顶点导出子图$ G_1 $上是$ G_1 $的符号边控制函数, 由$ G_1\cong P_3\times P_{n-1} $及归纳假设知,

$ S_f=1+S_{f_{G_1}}\leq 1+\left \lfloor \frac{3(n-1)+\left \lfloor \frac{n-2}{3} \right \rfloor-3}{2} \right \rfloor\le\left \lfloor \frac{3n+\left \lfloor \frac{n-1}{3} \right \rfloor-3}{2} \right \rfloor. $

综上对$ n\geq 4 $, 有$ S_f\leq \left \lfloor \frac{3n+\left \lfloor \frac{n-1}{3} \right \rfloor-3}{2} \right \rfloor $, 从而结论成立.

定理2.3  设$ G={P_4}\times{P_n}\left ( n\ge 4\right ) $且$ n\equiv i\; ( \text{mod}\; 2) $, 则$ {\gamma}_{s}^{'}(G)= 2n+3+i. $

证  定义图$ G $的一个$ E\left ( G \right ) $到$ \left \{ -1, 1 \right \} $的函数$ g $如下:

$ g(e) =\left\{\begin{array}{ll} -1, & e=v_{j}^{i}v_{j+1}^{i}, i\equiv1\left ( \text{mod}\; 2 \right ) 且 i\neq 1, n, j=1, 2, 3 ;\\ -1, & e=v_{j}^{i}v_{j+1}^{i}, i\equiv0\left ( \text{mod}\; 2 \right ) 且 \; i\neq n, j=1, 3 ;\\ -1, & e=v_{j}^{i}v_{j+1}^{i}, i=1 或 i=n\equiv1\left ( \text{mod}\; 2 \right ) 且 j=2 ;\\ 1, &\text{其他}. \end{array}\right. $

易验证$ g $是$ G $的符号边控制函数, 且$ {\gamma}_{s}^{'}(G)\leq g(E(G))= 2n+3+i. $

下面证$ {\gamma}_{s}^{'}(G)\ge 2n+3+i $. 设$ f $是$ G $的最小符号边控制函数, 只需证$ S_{f}\le \bigg\lceil\frac{5n-8}{2}\bigg\rceil. $对$ n\geq 4 $应用数学归纳法. 当$ n=4 $时, 可验证$ S_{f} $=6, 结论成立. 假设对于大于$ 4 $小于$ n $的整数成立, 下证结论对$ n $也成立.

断言  与$ G $的第$ 1, n $列顶点关联的边至多有$ 2 $条在$ f $下值为$ -1 $, 与$ G $的前2列和后2列顶点关联的边至多有$ 4 $条在$ f $下值为$ -1 $.

情形1  $ G $中存在两条相邻的边在$ f $下值为$ -1 $. 不妨设$ f $是使满足上述条件的两条边所关联顶点的最小上标$ i $尽可能小的$ G $的最小符号边控制函数, 则$ 2\le i\le n-2 $. 记$ G^1 $和$ G^2 $为满足$ G=G^1\cup G^2 $, $ V(G^1)\cap V(G^2)=\left\{ v_{1}^{i}, v_{2}^{i}, v_{3}^{i}, v_{4}^{i} \right\} $的子图, $ G_{1} $和$ G_{2} $为满足$ G=G_{1}\cup G_{2} $, $ V(G_{1})\cap V(G_{2})=\left\{ v_{1}^{i+1}, v_{2}^{i+1}, v_{3}^{i+1}, v_{4}^{i+1} \right\} $的子图, 因而$ G^1\cong P_4\times P_i $, $ G^2\cong P_4\times P_{n-i+1} $, $ G_{1 }\cong {P_4}\times{P_{i+1}} $, $ G_{2 }\cong {P_4}\times{P_{n-i}} $.

情形1.1  $ f\left ( v_{1}^{i}v_{2}^{i} \right )=f\left ( v_{2}^{i}v_{3}^{i} \right )=-1 $或$ f\left ( v_{2}^{i}v_{3}^{i} \right )=f\left ( v_{3}^{i}v_{4}^{i} \right )=-1 $. 两者可能同时出现. 由对称性, 不妨设前者必出现, 则与$ v_1^{i-1}, v_1^{i+1} $, $ v_2^{i-1}, v_2^{i+1} $关联的边中至多有1条$ f $值为$ -1 $. 定义$ f^{t}:E\left ( G^t \right ) \rightarrow \{-1, +1\} $ $ (t=1, 2) $如下:

$ \begin{eqnarray*} f^{1}(e) =\left\{\begin{array}{ll} 1, & e\in \left\{ v_{1}^{i}v_{2}^{i}, v_{2}^{i}v_{3}^{i}, v_{3}^{i}v_{4}^{i} \right\} ;\\ -1, & e=v_2^{i-1}v_2^{i} ;\\ f(e), &\text{其他}. \end{array}\right. f^{2}(e) =\left\{\begin{array}{ll} 1, & e\in \left\{ v_{1}^{i}v_{2}^{i}, v_{2}^{i}v_{3}^{i}, v_{3}^{i}v_{4}^{i} \right\} ;\\ -1, & e=v_2^{i}v_2^{i+1} ;\\ f(e), &\text{其他}. \end{array}\right. \end{eqnarray*} $

当$ i\ge 4 $且$ n-i\ge 3 $时, 可验证$ f^{t} $是$ G^{t} $的符号边控制函数, 且$ S_{f}\le S_{f^{1}}+S_{f^{2}}+1. $由归纳假设知,

$ S_{f}\le\bigg\lceil\frac{5i-8}{2}\bigg\rceil +\bigg\lceil\frac{5(n-i+1)-8}{2}\bigg\rceil+1\le \bigg\lceil\frac{5n-8}{2}\bigg\rceil. $

当$ i=2 $或$ n-i=1 $时, 若$ f(v_3^2v_4^2)=-1 $, 则与$ G^1 $的第一列或$ G^2 $第$ n $列关联的$ f $值为$ -1 $的边至多有1条, 由归纳假设仍可证结论成立; 若$ f(v_3^2v_4^2)=1 $, $ S_{f}= S_{f^{1}}+S_{f^{2}} $, 由断言及归纳假设仍可验证结论成立. 当$ i=3 $或$ n-i=2 $时, $ G^1 $的前两列或$ G^2 $后两列关联的$ f $值为$ -1 $的边至多有3条, 由归纳假设知,

$ S_{f}\le 4 +\bigg\lceil\frac{5(n-2)-8}{2}\bigg\rceil+1= \bigg\lceil\frac{5n-8}{2}\bigg\rceil. $

情形1.2  存在$ j\in\{1, 2, 3, 4\} $, 使得$ f(v_{j}^{i}v_{j}^{i+1})=f(v_{j}^{i+1}v_{j}^{i+2})=-1 $. 此时$ n-i\ge 3 $. 不妨设$ j=1 $, 由符号边控制函数的定义知, 与$ v_{2}^{i+1} $关联的边在$ f $下值均为$ 1 $且$ N_{G}[v_{3}^{i+1}v_{4}^{i+1}] $中至多有两条边在$ f $下值为$ -1 $. 当$ f\left ( v_{3}^{i+1}v_{4}^{i+1} \right )=1 $时, 若$ v_{3}^{i}v_{3}^{i+1}, v_{4}^{i}v_{4}^{i+1} $和$ v_{3}^{i+1}v_{3}^{i+2}, v_{4}^{i+1}v_{4}^{i+2} $的$ f $下值都不同时为$ -1 $或$ f\left ( v_{3}^{i}v_{3}^{i+1} \right )=f\left ( v_{4}^{i}v_{4}^{i+1} \right )=-1 $, 则$ f\mid_{G_{2}} $是$ G_{2} $的符号边控制函数, $ M=\{e\in E(G_1)|f(e)=-1\} $是$ G_1 $的匹配, 且$ S_{f}=|M|+S_{f \mid _{G_{2} }} $. 因为存在$ N_G[v_1^1], N_G[v_4^4] $的点及$ v_2^{i+1} $在$ M $下非饱和, 所以$ |M|\le\frac{4(i+1)-4}{2} $, 从而当$ n-i\ge 4 $时, 由归纳假设知,

$ \begin{eqnarray*} S_{f}\le \frac{4(i+1)-4}{2} +\bigg\lceil\frac{5(n-i)-8}{2}\bigg\rceil \le\bigg\lceil\frac{5n-8}{2}\bigg\rceil. \end{eqnarray*} $

当$ n-i\le 3 $时, 由断言及归纳假设仍可验证结论成立.

若$ f\left ( v_{3}^{i+1}v_{3}^{i+2} \right )=f\left ( v_{4}^{i+1}v_{4}^{i+2} \right )=-1 $, 由情形1.1及$ i $的选取, 不妨设与$ v_3^i $关联的边中至多有1条值为$ -1 $, 则$ M=\{e\in E(G_1)|f(e)=-1\} $是$ G_1 $的匹配, 且至少有6个点非饱和, 因此$ |M|\le\frac{4(i+1)-6}{2} $. 在$ G_2 $中令$ f'(v_4^{i+1}v_4^{i+2})=1 $, 其他边$ e $, $ f'(e)=f(e) $, 则$ f' $是$ G_2 $的符号边控制函数, 当$ n-i\ge 4 $时, 由归纳假设知,

$ \begin{eqnarray*} S_{f}\le \frac{4(i+1)-6}{2}+1+\bigg\lceil\frac{5(n-i)-8}{2}\bigg\rceil \le\bigg\lceil\frac{5n-8}{2}\bigg\rceil. \end{eqnarray*} $

当$ n-i\le 3 $时, 由断言及归纳假设仍可验证结论成立.

当$ f\left ( v_{3}^{i+1}v_{4}^{i+1} \right )=-1 $时, 定义图$ G $的一个$ E\left ( G \right ) $到$ \left \{ -1, 1 \right \} $的函数$ f^{'} $如下:

$ f^{'}(e) =\left\{\begin{array}{ll} 1, & e= v_{3}^{i+1}v_{4}^{i+1} ;\\ f(e), &\text{其他}. \end{array}\right. $

可验证$ f^{'} $是$ G $的符号边控制函数, $ S_{f'}=S_{f }-1 $且$ f^{'} \mid _{G_{1} } $和$ f^{'} \mid _{G_{2} } $分别是$ G_{1} $和$ G_{2} $的符号边控制函数, 当$ i\ge 3 $且$ n-i\ge 4 $时, 由$ S_{f^{'} }=S_{f^{'} \mid _{G_{1} }}+S_{f^{'} \mid _{G_{2} }} $及归纳假设知,

$ \begin{eqnarray*} S_{f}\le\bigg\lceil\frac{5(i+1)-8}{2}\bigg\rceil +\bigg\lceil\frac{5(n-i)-8}{2}\bigg\rceil+1 \le \bigg\lceil\frac{5n-8}{2}\bigg\rceil. \end{eqnarray*} $

当$ i=2 $时, 由$ i $的选取知, $ S_{f'|_{G_1}}\le 3 $, 再由归纳假设可证明结论成立. 当$ n-i=3 $时, 由断言及归纳假设仍可证明结论成立.

类似可证当$ f\left ( v_{j}^{i}v_{j}^{i+1} \right )=f\left ( v_{j}^{i+1}v_{j}^{i+2} \right )=-1, \; j=2, 3, 4 $时结论成立.

情形1.3  $ f\left ( v_{j}^{i}v_{j+1}^{i} \right )=f\left ( v_{j+1}^{i}v_{j+1}^{i+1} \right )=-1 $或$ f\left ( v_{j}^{i}v_{j+1}^{i} \right )=f\left ( v_{j}^{i}v_{j}^{i+1} \right )=-1 $ $ (j=1, 2, 3) $. 由情形1.1, 不妨设$ G $的第$ i $列顶点导出子图的值为$ -1 $的边两两不相邻. 由$ i $的选取知, $ G^1 $的在$ f $下值为$ -1 $的边构成$ G^1 $的匹配$ M $. 因为$ N_G[v_1^1] $和$ N_G[v_4^1] $都至少有一个点不与$ M $中边关联, 所以$ |M|\le \frac{4i-2}{2} $且当$ i=2 $时, 由$ v_{j+1}^2 $或$ v_j^2 $关联2条$ -1 $边知$ |M|\le 2 $. 定义$ f':E(G^2)\rightarrow \{1, -1\} $如下:

$ f^{'}(e) =\left\{\begin{array}{ll} 1, & e\in\{v_j^iv_{j+1}^i|j=1, 2, 3\} ;\\ f(e), &\text{其他}. \end{array}\right. $

可验证$ f^{'} $是$ G^2 $的符号边控制函数, 且$ S_{f}=|M|+S_{f'} $. 当$ n-i\ge 4 $时, 由归纳假设知,

$ \begin{eqnarray*} S_{f}\le \left\{\begin{array}{ll} \frac{4i-2}{2}+\bigg\lceil\frac{5(n-i+1)-8}{2}\bigg\rceil, & i\ge 3 \\ 2+\bigg\lceil\frac{5(n-2+1)-8}{2}\bigg\rceil, & i=2 \end{array}\right. \le \bigg\lceil\frac{5n-8}{2}\bigg\rceil. \end{eqnarray*} $

当$ n-i\le 3 $时, 由断言仍可证明结论成立.

情形1.4  存在$ j\in\{1, 2, 3\} $, 使得$ f\left ( v_{j}^{i}v_{j}^{i+1} \right )=f\left ( v_{j}^{i+1}v_{j+1}^{i+1} \right )=-1 $或存在$ j\in\{2, 3, 4\} $, 使得$ f\left ( v_{j}^{i}v_{j}^{i+1} \right )=f\left ( v_{j}^{i+1}v_{j-1}^{i+1} \right )=-1 $. 显然若前者成立, 则由对称性可知后者也成立. 对前者当$ j=1 $时, 若$ f(v_2^{i-1}v_2^i)=-1 $或$ f(v_2^iv_3^i)=-1 $, 则交换$ v_1^iv_1^{i+1} $和$ v_1^iv_2^i $的$ f $值得到的$ f' $是$ G $的最小符号边控制函数, 且要么$ f' $下两条相邻值为$ -1 $的边的下标比$ i $小, 矛盾于$ f $的选取, 要么由情形1.1知结论成立; 当$ f(v_2^{i-1}v_2^i)=f(v_2^iv_3^i)=1 $时, 定义图$ G $的一个$ E\left ( G \right ) $到$ \left \{ -1, 1 \right \} $的函数$ f^{'} $如下:

$ f^{'}(e) =\left\{\begin{array}{ll} -f(e), & e\in\{ v_1^iv_2^i, v_2^iv_2^{i+1}, v_{1}^{i}v_{1}^{i+1}, v_1^{i+1}v_2^{i+1}\} 且 f(v_3^iv_4^i)=1 ;\\ -f(e), & e\in\{ v_1^iv_2^i, v_2^iv_3^i, v_{1}^{i}v_{1}^{i+1}, v_3^{i}v_4^{i}\} 且 f(v_3^iv_4^i)=-1 ;\\ f(e), &\text{其他}. \end{array}\right. $

由$ i $的选取可验证$ f^{'} $是$ G $的最小符号边控制函数, 且或$ f'(v_1^iv_2^i)=f'(v_2^iv_2^{i+1})=-1 $或$ f'(v_1^iv_2^{i})=f'(v_2^{i}v_3^{i})=-1 $, 由情形1.3或情形1.1知结论成立.

当$ j=2 $时, $ N_{G}[v_{3}^{i+1}v_{4}^{i+1}]- \left\{ v_{2}^{i+1}v_{3}^{i+1} \right\} $中至多有$ 1 $条边在$ f $下值为$ -1 $. 由情形1.1-情形1.3和$ i $的选取知, 不妨设$ f(v_1^iv_2^i)=f(v_2^iv_3^i)=1 $且与$ v_3^i $关联的边中至多有一条为$ -1 $, 则在$ G^2 $中与$ v_1^i, v_1^{i+1} $关联的边在$ f $下值均为1, 从而当$ f(v_3^{i}v_4^{i})=1 $时, $ f|_{G^2} $是$ G^2 $的符号边控制函数. 由$ M=\{e\in E(G^1)|f(e)=-1\} $是$ G^1 $的匹配及至少有4个顶点不饱和知,

$ |M|\le\left\{\begin{array}{ll} \frac{4i-4}{2}, & i\ge 3 ;\\ 2, &i=2. \end{array}\right. $

因此当$ n-i\ge 3 $时, 由归纳假设知,

$ \begin{eqnarray*} S_{f}\le \left\{\begin{array}{ll} \frac{4i-2}{2}+\bigg\lceil\frac{5(n-i+1)-8}{2}\bigg\rceil, & i\ge 3 \\ 2+\bigg\lceil\frac{5(n-2+1)-8}{2}\bigg\rceil, & i=2 \end{array}\right. \le \bigg\lceil\frac{5n-8}{2}\bigg\rceil. \end{eqnarray*} $

当$ n-i=2 $时, 由断言知结论成立. 当$ f(v_3^{i}v_4^{i})=-1 $时, 由情形1.3, 不妨设$ f(v_4^iv_4^{i+1})=1 $, 则交换$ v_2^{i+1}v_3^{i+1} $和$ v_3^iv_3^{i+1} $的$ f $值得到的$ f' $是$ G $的符号边控制函数, 且$ f'(v_3^{i}v_4^{i})=f'(v_3^iv_3^{i+1})=-1 $, 由情形1.3知, 结论成立.

$ j=3 $时, 由$ i $的选取, 情形1.1, 情形1.2, 情形1.3, 及前面$ j=1, 2 $的证明可设$ f(v_2^iv_3^i)=1 $, 且与$ v_j^i $关联的边中至多有一条$ f $值为$ -1 $, $ j=1, 2, 3, 4 $. 若$ f(v_1^{i-1}v_1^i), f(v_2^{i-1}v_2^i) $和$ f(v_1^{i}v_1^{i+1}), f(v_2^{i}v_2^{i+1}) $都不同时为$ -1 $, 则$ f|_{G^1} $是$ G^1 $的符号边控制函数. 定义图$ G^2 $的一个$ E\left ( G^2 \right ) $到$ \left \{ -1, 1 \right \} $的函数$ f^{'} $如下:

$ f^{'}(e) =\left\{\begin{array}{ll} 1, & e=v_{1}^{i}v_{2}^{i} 且 f(e)=-1 ;\\ f(e), &\text{其他}. \end{array}\right. $

可验证$ f^{'} $是$ G^2 $的符号边控制函数, 且$ S_f\le S_{f|_{G^1}}+S_{f'} $, 当$ i\ge 4 $且$ n-i\ge 3 $时, 由归纳假设可证结论成立. 当$ i\le 3 $或$ n-i= 2 $时, 由断言及归纳假设仍可证明结论成立. 若$ f(v_1^{i-1}v_1^i)=f(v_2^{i-1}v_2^i)=-1 $, 则$ f|_{G^2} $是$ G^2 $的符号边控制函数. 同情形1.3的讨论知,

$ |\{e\in E(G^1)|f(e)=-1\}|\le\left\{\begin{array}{ll} \frac{4i-2}{2}, & i\ge 3 ;\\ 2, &i=2. \end{array}\right. $

因此当$ n-i\ge 3 $时, 由归纳假设知,

$ \begin{eqnarray*} S_{f}\le \left\{\begin{array}{ll} \frac{4i-2}{2}+\bigg\lceil\frac{5(n-i+1)-8}{2}\bigg\rceil, & i\ge 3 \\ 2+\bigg\lceil\frac{5(n-2+1)-8}{2}\bigg\rceil, & i=2 \end{array}\right. \le \bigg\lceil\frac{5n-8}{2}\bigg\rceil. \end{eqnarray*} $

当$ n-i=2 $时, 由断言仍可证明结论成立.

若$ f(v_1^{i}v_1^{i+1})=f(v_2^{i}v_2^{i+1})=-1 $, 则定义图$ G $的一个$ E\left ( G \right ) $到$ \left \{ -1, 1 \right \} $的函数$ f^{'} $如下:

$ f^{'}(e) =\left\{\begin{array}{ll} 1, & e=v_{1}^{i}v_{1}^{i+1};\\ f(e), &\text{其他}. \end{array}\right. $

可验证$ f^{'} $是$ G $的符号边控制函数, $ S_{f'}= S_f-1 $且$ f'|_{G^i} $ $ (i=1, 2) $是$ G^i $的符号边控制函数. 当$ i\ge 4 $且$ n-i\ge 3 $时, 由归纳假设知,

$ \begin{eqnarray*} S_{f}\le \bigg\lceil\frac{5i-8}{2}\bigg\rceil+\bigg\lceil\frac{5(n-i+1)-8}{2}\bigg\rceil+1\le \bigg\lceil\frac{5n-8}{2}\bigg\rceil. \end{eqnarray*} $

由$ i $的选取知当$ i=2 $时, 与$ G $的第1列关联的值为$ -1 $的边至多有1条; 当$ i=3 $或$ n-i=2 $时, 与$ G $的前两列或后两列关联的$ f' $值为$ -1 $的边至多有3条, 由归纳假设结论仍成立.

情形2  在$ f $下值为$ -1 $的边两两不相邻, 此时值为$ -1 $的边构成$ G $的一个匹配, 由于$ v_{1}^{1}, v_{4}^{1}, v_{1}^{n}, v_{4}^{n} $是$ 2 $度点, 与它们相邻的点又都是$ 3 $度点, 所以$ G $中至少有$ 4 $个顶点不关联值为$ -1 $的边, 从而

$ \begin{eqnarray*} S_{f}\le \frac{4n-4}{2} =\frac{5n-(n+4)}{2} \le \bigg\lceil\frac{5n-8}{2}\bigg\rceil. \end{eqnarray*} $

因此$ n\geq 4 $, $ S_{f}\le \bigg\lceil\frac{5n-8}{2}\bigg\rceil. $从而结论成立.

猜想  设$ G={P_m}\times{P_n}\left ( n\ge m\ge 4\right ) $, 则

$ {\gamma}_{s}^{'}(G)=2mn-m-n-2\bigg(\bigg\lceil\frac{n}{2}\bigg\rceil(m-1)+\bigg\lceil\frac{n-5}{2}\bigg\rceil\bigg\lceil\frac{m-1}{2}\bigg\rceil\bigg). $

由定理2.3的证明可知上述猜想对$ m=4 $是成立的.