所谓图$G$的一个$m$ -边赋权是指从$G$的边集$E(G)$到权集合$\{1, 2, \cdots, m\}$的一个映射.称$\{$$1, 2$, $\cdots, m$$\}$里的每个数为对$G$进行边赋权所使用的权, $w$是$G$的一个边赋权, 对$G$的每条边$e$, 在$w$下$e$的象$w(e)$称为$e$在$w$下的权.对图$G$的每个顶点$v$来说, 用$\tilde{S}(v)$表示与$v$关联的所有边的权构成的多重集, 称$\tilde{S}(v)$为$v$的权集.

$\tilde{S}(v)$中全体元素的和记为$w(v)$, 即

$ w(v)=\sum\limits_{j \in \tilde{S}(v)}j, $

称$w(v)$为$v$在$G$的边赋权$w$下的权度.

若$w$是$G$的一个$m$ -边赋权, 且对$G$中任意两个不同的顶点$u$和$v$, 都有$w(u)$$\neq$$w(v)$, 则称$G$的$m$ -边赋权$w$是允许的或称$w$为$G$的一个$m$ -非正规分配.使得$G$存在$m$ -非正规分配的最小的正整数$m$称为$G$的非正规强度, 记为$s(G)$, 即$~s(G)$=$\min$$\{$$m$$\mid$$G$存在$m$ -非正规分配$\}$.

显然, $G$存在非正规强度当且仅当$G$存在非正规分配, 亦即当且仅当$G$没有孤立边且最多只有一个孤立点.

图的非正规强度这一概念是由Chartrand, Jacobson, Lehel, Oellerman, Ruiz和Saba于1986年提出的(参见文献[1]), 此后在文[2-8]中均有研究.在文[1]中得到了重要结论:“对任意没有孤立边且最多只有一个孤立点的简单图$G$来说, $s(G$)$\leq 2n-3$”, 在文[2]中得到了结论:“阶数为$n(n\geq4)$的连通图$G$的非正规强度$s(G)\leq n-1$, 且对$n$阶星有$s(St_{n})= n-1$”, 在文[3]中对$t$条3阶路的点不交的并的非正规强度进行了研究, 得到了如下结论:

定理 A^[3]  $\lceil\dfrac{15t-1}{7}\rceil$ $\leq$ $s($ $tP_{3}$ $)$ $\leq$ $\lceil\dfrac{15t-1}{7}\rceil +1$.

Kinch和Lehel在文[3]中猜想$s($ $tP_{3}$ $)$=$\lceil\frac{15t-1}{7}\rceil$, 但是, Aigner和Triesch于1990年在文[4]中对此问题进行了彻底的解决, 给出了下述定理B.

定理 B^[4]  $s($ $tP_{3}$ $)$=$\lceil\dfrac{15t-1}{7}\rceil$, 除非当$n\equiv45, ~66$~(mod~84) 时, $s($ $tP_{3}$ $)$=$\lceil\dfrac{15t-1}{7}\rceil$ +1.

而后, Cahit和Tezer于1998年在文[5]中对若干点不交的$n$阶路的并图的非正规强度进行了研究, 得到了以下结论:

定理 C^[5]  $s(t{P_n}) = \left\{ \begin{array}{l} \;\;\;\frac{{tn}}{2},\;\;\;\;\;\;\;\;\;n \equiv 0\;\left( {\bmod \;4} \right);\\ \;\left\lfloor {\frac{{tn}}{2}} \right\rfloor + 1,\;\;\;\;n \equiv 1\;\left( {\bmod \;4} \right). \end{array} \right.$

定理 D^[5]  当$n\equiv2$ (mod 4) 时, 若$t\equiv0$ (mod 2), 则$s(tP_{n})=\frac{tn}{2}$; 若$t\equiv 1$ (mod 2), 则$s(tP_{n})\leq\frac{tn}{2}+1.$

但是, 在定理C中, 关于$tP_{n}(n \equiv 1$ (mod 4))的非正规强度的结果不正确, 因为在$(t\equiv 0$ (mod 4))时结果应该为$\frac{tn}{2}$.

在文献[6-7]中, 分别对正则图和有向图的非正规强度进行了研究.文献[8]中, 对任意两个度不为2的点的距离至少是8的树$T$进行了研究, 得到了结论:“$s(T)=\lceil\frac{n_{1}+n_{2}}{2}\rceil$, $n_{1}\geq3$, 其中$n_{i}$表示树$T$中度为$i$的顶点的个数”.

在本文中, 我们利用构造矩阵的方法精确求出了$tP_{n}$ ($n\equiv1$ (mod 4))的非正规强度.

需要注意的是, 对$tP_{n}$进行$m-$边赋权时, 每个点的权度$w(v)$, 要么是权集合$\{1, 2, \cdots, m\}$中的一个数, 要么是权集合$\{1, 2, \cdots, m\}$中两个数(可以相同)的和.

引理 1^[5]  设$F(P_{i_{1}}, P_{i_{2}}, \cdots, P_{i_{k}})$表示由路$P_{i_{1}}, P_{i_{2}}, \cdots, P_{i_{k}}$的点不交的并构成的森林, 则$F$的非正规强度的下界为

$ \max\{\frac{|V|}{2}, |V_{e}|\}\leq s(F(P_{i_{1}}, P_{i_{2}}, \cdots, P_{i_{k}})), $

其中$|V_{e}|$表示$F$中端点的个数.

定理 1  设$n\geq 5$, 且$n\equiv1$ (mod 4), 则

$ s(t{P_n}) = \left\{ \begin{array}{l} \;\;\;\frac{{tn}}{2},\;\;\;\;\;\;\;\;\;t \equiv 0\;\left( {\bmod \;4} \right),\\ \;\left\lfloor {\frac{{tn}}{2}} \right\rfloor + 1,\;\;\;\;t\not\equiv1\;\left( {\bmod \;4} \right), \end{array} \right.\;\;\;\;\;\left( {t \ge 2} \right). $

证  当$t\equiv0$ (mod 4) 时, $tP_{n}$中所有顶点的个数为$tn$, 由引理1知$s(tP_{n}) \geq \frac{tn}{2}$.

当$t\equiv1, 3$ (mod 4) 时, $tP_{n}$中所有顶点的个数为$tn$, 是一个奇数, 则至少需要使用$\frac{tn+1}{2}$个数进行边赋权, 即

$ s(tP_{n})\geq \frac{tn+1}{2}=\lfloor\frac{tn}{2}\rfloor +1. $

当$t\equiv2$ (mod 4) 时, 假设$tP_{n}$存在$\frac{tn}{2}$ -边赋权, 则在$w$下, 所有点可能产生的权度依次为$1, 2, \cdots, tn$, 所有点的权度之和为$\frac{tn(tn+1)}{2}$, 由于$\frac{tn}{2}$和$tn+1$都是奇数, 即$\frac{tn(tn+1)}{2}$也是奇数.这与所有点的权度之和等于边的权之和的2倍, 是一个偶数相矛盾！故$s(tP_{n}) \geq \frac{tn}{2}+1$.

下面分$n=5$和$n\geq9 (n\equiv1$ (mod 4))两种情况来讨论.

(1) 当$n=5$时, 如图 1所示, 只需分别给出$t\equiv0$ (mod 4) 和$t\not\equiv 0$ (mod 4) 时, $tP_{5}$的$\frac{5t}{2}$ -边赋权和$(\lfloor\frac{5t}{2}\rfloor+1)$ -边赋权即可.

(2) 当$n\geq9, $且$n\equiv1$ (mod 4) 时, 用一个$t\times(n-1)$矩阵$\mathbf{M}$表示$tP_{n}$的所有边的权.若$t\equiv0$ (mod 4), 与$tP_{n}$相应的矩阵$\mathbf{M_{1}}$为

给第$h$条路$u_{1}^{(h)}u_{2}^{(h)}$$\cdots$$u_{n-1}^{(h)}u_{n}^{(h)}$上的边, 依次用$\mathbf{M_{1}}$中的第$h$行的元素赋权, $h=1, 2, \cdots, t$, 得到了$tP_{n}$的$\frac{tn}{2}$ -边赋权$w$.在$w$下, 所有点的权度依次为$1, 2, \cdots, tn, $因此, $w$是非正规分配.所以, 当$t\equiv0$ (mod 4) 时, $s(tP_{n})=\frac{tn}{2}.$

若$t\equiv1$ (mod 4), 与$tP_{n}$相应的矩阵$\mathbf{M_{2}}$为

给第$i$条路$u_{1}^{(i)}u_{2}^{(i)}$$\cdots$$u_{n-1}^{(i)}u_{n}^{(i)}$上的边, 依次用$\mathbf{M_{2}}$中的第$i$行的元素赋权, $i=1, 2, \cdots, t$, 得到了$tP_{n}$的$\frac{tn+1}{2}$ -边赋权$w$.在$w$下, 除了$(n-3)t+1$不是任何点的权度之外, 其余从$1$到$tn+1$的每个数都是某个点的权度.这说明所给的$ \frac{tn+1}{2}$ -边赋权是非正规分配.所以, $s(tP_{n})=\lfloor\frac{tn}{2}\rfloor+1.$

若$t\equiv2$ (mod 4), 与$tP_{n}$相应的矩阵$\mathbf{M_{3}}$为

给第$j$条路$u_{1}^{(j)}u_{2}^{(j)}$$\cdots$$u_{n-1}^{(j)}u_{n}^{(j)}$上的边, 依次用$\mathbf{M_{3}}$中的第$j$行的元素赋权, $j=1, 2, \cdots, t$, 得到了$tP_{n}$的$(\frac{tn}{2}+1)$ -边赋权$w$.在$w$下, 除了$(n-3)t+1$和$(n-3)t+3$不是任何点的权度之外, 其余从$1$到$tn+2$的每个数都是某个点的权度.这说明所给的$(\frac{tn}{2}+1)$ -边赋权是非正规分配.所以, $s(tP_{n})= \frac{tn}{2}+1.$

若$t\equiv3$ (mod 4), 与$tP_{n}$相应的矩阵$\mathbf{M_{4}}$为

给第$k$条路$u_{1}^{(k)}u_{2}^{(k)}$$\cdots$$u_{n-1}^{(k)}u_{n}^{(k)}$上的边, 依次用$\mathbf{M_{4}}$中的第$k$行的元素赋权, $k=1, 2, \cdots, t$, 得到了$tP_{n}$的$\frac{tn+1}{2}$ -边赋权$w$.在$w$下, 除了$\frac{(n-3)t}{2}+1$不是任何点的权度之外, 其余从$1$到$tn+1$的每个数都是某个点的权度.这说明所给的$\frac{tn+1}{2}$ -边赋权是非正规分配.所以$s(tP_{n})=\frac{tn+1}{2}=\lfloor\frac{tn}{2}\rfloor+1.$