树的反魔幻标号

Anti-Magic Labeling of Trees

摘要: 一个简单图$G=\left(V,E\right)$ 的反魔幻标号是一个双射$f:E\to \left\{1,2,\cdots ,\left|E\right|\right\}$ ，使得任意顶点所关联的边的标号之和互不相同。如果一个图存在魔幻标号，则称其为反魔幻图。Hartsfield和Ringel猜想除$K_2$ 以外的所有树图都是反魔幻的。令T是一个非$K_2$ 的树图，$V_2\left(T\right)$ 是T中所有顶点度为2的顶点集合。Liang，Wong和Zhu证明了若由$V_2\left(T\right)$ 所得的诱导子图是一条路径P，且T中所有不属于$V_2\left(T\right)$ 里的顶点的度均为奇数，则T是反魔幻图。令$v_s$ 是路径P的中间点，且v是不属于T的一个新的顶点。设T'是通过连接$v_s$ 和v由T所构造的新树。本文证明了T'仍保持反魔幻性。

Abstract: Let $G=\left(V,E\right)$ be a simple graph. A bijection $f:E\to \left\{1,2,\cdots ,\left|E\right|\right\}$ is called anti-magic if the sum of labels of the edges incident to any vertex is distinct. A graph is called anti-magic if there exists anti-magic labeling. Hartsfield and Ringel conjected that every tree other than $K_2$ has an anti-magic labeling. Let T be a tree not $K_2$ and $V_2\left(T\right)$ be the set of vertices of degree 2 in T. Liang, Wong and Zhu showed that if the induced subgraph of $V_2\left(T\right)$ is a path P and the degree of any vertex in $V\left(T\right)\backslash V_2\left(T\right)$ is odd, then T is anti-magic. Suppose that $v_s$ is the middle vertex of P and v is a new vertex. T' is a new tree obtained from T by joining $v_s$ and v. In this paper, we prove that T' is also anti-magic.

1. 引言

对于一个简单图$G=\left(V,E\right)$ ，双射$f:E\to \left\{1,2,\cdots ,\left|E\right|\right\}$ 是图$G$ 的边标号。对于图$G$ 中的任意顶点$u$ ，$u$ 的标号是所有与$u$ 相关联的边的标号之和，表示为${\phi }_f\left(u\right)={\displaystyle \sum _{e\in E(u)}f\left(e\right)}$ 。Hartsfield和Ringel [1]提出了反魔幻问题。如果对于图$G$ 中任意两个不同的顶点$u$ 和$v$ ，都有${\phi }_f\left(u\right)\ne {\phi }_f\left(v\right)$ ，那么标号$f$ 就是图$G$ 的反魔幻标号。如果一个图有反魔幻标号，那就称其是反魔幻图。$K_2$ 是由两个顶点及连接它们的一条边构成的简单图。很明显，$K_2$ 不是反魔幻图。

在图论中，图的标号问题一直是一个重要的研究领域。与传统的幻方问题不同，反魔幻标号关注的是图中各顶点标号和的差异性，而非保持一致性。因此，反魔幻标号不仅揭示了图的结构的多样性，也推动了对图对称性和优化特性的深入探讨。对于简单图来说，双射的边标号可以为研究图的标号问题提供一个新的视角。反魔幻标号问题由Hartsfield和Ringel [1]提出，并且提出了相关的猜想。

猜想1. ([1]) 至少含有两条边的连通图是反魔幻图。

猜想2. ([1]) 至少含有两条边的树图是反魔幻图。

这些猜想引起了广泛关注，特别是在树的反魔幻标号方面的研究。树是图论中最基本的结构之一，树的反魔幻标号问题不仅拓展了图论的研究范畴，而且为树的拓扑结构和性质提供了更为丰富的理解。近年来，许多学者利用不同的数学方法，结合概率论、解析数论和组合技术，取得了一系列进展。尽管有一些特殊的图类型已被证明是反魔幻的，但对于大部分图，尤其是一般树图的反魔幻标号问题，仍未得到完全解决。对于无向图来说，顶点的度是指与该顶点相关联的边的数量。图中的度数在很多情况下决定了图的结构和性质，对于树图的分析尤其重要。Kaplan, Lev和Roditty [2]提出了用零和分割证明最多含有一个二度顶点的树是反魔幻图的方法。Liang, Wong和Zhu [3]则将结果拓展到含有多个二度顶点的树图上。蜘蛛图和毛毛虫图都是特殊的树图。蜘蛛图是含有一个度至少为3的顶点，其他所有顶点的度至多为2的树图。毛毛虫图是在删除所有的叶子节点后，剩下的是路径图的树图。Shang [4]证明了所有的蜘蛛图都是反魔幻的。Lozano [5]等证明了毛毛虫图是反魔幻的。二项树和斐波那契树都是通过递归构建的。二项树$B_k$ 是通过连接两个$k-1$ 阶二项树$B_{k-1}$ 的根节点得到的。我们将$B_{k-1}$ 中的一个叶子节点看作根节点。阶数为0的二项树$B_0$ 只是一个单节点，而阶数为1的二项树$B_1$ 是一个包含两个节点的树。对于斐波那契树$F_k$ ，$F_0$ 和$F_1$ 分别是单节点树和包含两个节点的树，而$F_k$ 是由一个新的顶点和两个更小的斐波那契树$F_{k-1}$ 和$F_{k-2}$ 连接而成，使得新的顶点作为根节点分别与$F_{k-1}$ 和$F_{k-2}$ 的根节点相邻。Sethuraman和Shermily [6]证明了二阶以上的二项树和斐波那契树是反魔幻的。对于树图的研究也引起了学者对森林图的关注，对各类森林图的反魔幻标号可以在[7] [8]中被找到。

给定图$G=\left(V,E\right)$ ，$G^{\prime }=\left(V^{\prime },E^{\prime }\right)$ ，如果$V^{\prime }\subseteq V$ ，$E^{\prime }\subseteq E$ ，则称 $G^{\prime }$ 是$G$ 的子图。如果$G$ 中任意使得$x,y\in V^{\prime }$ 的边$\left(x,y\right)$ 都在子图$G^{\prime }$ ，那么称图$G^{\prime }$ 为由$V^{\prime }$ 诱导的诱导子图。设$V_i\left(G\right)$ 为图$G$ 中度为$i$ 的顶点集合，$V_{even}\left(G\right)$ 为图$G$ 中所有的偶数度顶点的集合。Liang，Wong和Zhu [3]讨论了树图$T$ 在两种情况下是反魔幻的，一种是所有的二度顶点$V_2\left(T\right)$ 是相互独立的并且除二度顶点之外的所有顶点$V\left(T\right)\backslash V_2\left(T\right)$ 也是相互独立的，另一种是所有的二度顶点$V_2\left(T\right)$ 诱导出一条路径$P$ 。在第二种情况的证明方法中[3]，图的反魔幻标号是使顶点的标号与$\left|E\left(T\right)\right|+1$ 有关，并且路径$P$ 的中间点需要度的限制。故本文在第二种情况下考虑将$P$ 的中间点与一个孤立点相连，并进一步证明，这种改动不会破坏图的反魔幻性质。通过这种构造，图的反魔幻性得以维持。这种树图包含多个二度顶点，且结构与前述两种情况不同。特别的，新的构造方式展示了反魔幻性质如何在复杂结构下得到保持，从而丰富了我们对树图反魔幻性质的理解。本文的工作不仅验证了不同类型树图中反魔幻性的广泛适用性，而且扩展了树图反魔幻性研究的边界，为未来的研究提供了新的思路和方法。

2. 主要定理及证明

对于树图$T=\left(V\left(T\right),E\left(T\right)\right)$ ，我们将$T$ 中任意顶点$x$ 的度记为$\mathrm{deg}\left(x\right)$ 。假设$\left|E\left(T\right)\right|=m$ 且$V_{even}\left(T\right)$ 诱导出一条路径$P=\left(v_1,v_2,\cdots ,v_k\right)$ ，$k\ge 2$ 。由于路径的两个端点$v_1$ 和$v_k$ 是偶数度的顶点，所以除$v_2$ 和$v_{k-1}$ 之外仍存在$v_1$ 的邻点$v_0$ 以及$v_k$ 的邻点$v_{k+1}$ 且$P_0=\left(v_0,v_1,\cdots ,v_k,v_{k+1}\right)$ 也是一条路径，我们将路径$P_0$ 中的边记为$e_i=\left(v_{i-1},v_i\right)$ ，$i=1,2,\cdots ,k+1$ 。如果将路径$P_0$ 中的边从树图$T$ 中删除，我们将得到$k+2$ 个连通分支，我们用$\left(T_i,v_i\right)$ 表示$T-E\left(P_0\right)$ 中包含顶点$v_i$ 的分支，其中$i=0,1,\cdots ,k+1$ 。由于路径$P$ 的中间点与其长度有关，下面我们将路径$P$ 的长度分为奇数与偶数两种情况进行讨论。

引理3. ([5]) 对于一个树图，如果在删除所有的叶子节点后，剩下的是路径图，那么这个图是反魔幻图。即毛毛虫图是反魔幻图。

定理4. 设$T$ 是一个树图，$v$ 是一个孤立点，$V_{even}\left(T\right)$ 诱导出路径$P=\left(v_1,v_2,\cdots ,v_k\right)$ 且$\left|V_{even}\left(T\right)\right|=k$ 是奇

数，则$T+v_{s}v$ 是反魔幻的，其中$s=\frac{k+1}{2}$ 。

证明：首先对于路径$P_0=\left(v_0,v_1,\cdots ,v_k,v_{k+1}\right)$ 中的边$e_i$ 我们的标号为$f\left(e_{2j}\right)=j$ ，$f\left(e_{k+2-2j}\right)=m+1-j$ ，其中$j=1,2,\cdots ,s$ 。对于边$v_{s}v$ 进行标号$f\left(v_{s}v\right)=m+1$ 。那么顶点$v$ 的标号${\phi }_f\left(v\right)=m+1\equiv 0\left(\mathrm{mod}m+1\right)$ 。

对于$T-E\left(P_0\right)$ ，也就是${\displaystyle \underset{i=0}{\overset{k+1}{\cup }}\left(T_i,v_i\right)}$ 的边，用$\left[s+1,m-s\right]$ 区间内的整数进行标号。对于$i=0,1,\cdots ,k+1$ ，

我们将$\left(T_i,v_i\right)$ 看作以$v_i$ 为根的有向树，因为在$\left(T_i,v_i\right)$ 中$v_i$ 是偶数度的，所以$v_i$ 有偶数条出边。而除$v_i$ 外的所有顶点的度数都是奇数，所以它们都只有一条进边，偶数条出边。对于$\left(T_i,v_i\right)$ 中的任意顶点$u$ ，如果$u$ 的出边中存在边被标号为$t$ ，那么$u$ 的出边中也会有一条边被标号为$m+1-t$ 。

这样对于$\left(T_i,v_i\right)$ 中的任意除$v_i$ 之外的顶点$x$ 的标号${\phi }_f\left(x\right)\equiv f\left(e\right)\left(\mathrm{mod}m+1\right)$ ，其中$e$ 是顶点$x$ 的进边且$f\left(e\right)\in \left[s+1,m-s\right]$ 。

对于任意的$i\in \left\{1,2,\cdots ,s-1,s+1,\cdots ,k\right\}$ ，顶点$v_i$ 的标号${\phi }_f\left(v_i\right)=f\left(e_i\right)+f\left(e_{i+1}\right)+\frac{\mathrm{deg}\left(v_i\right)-2}{2}\left(m+1\right)$ ，${\phi }_f\left(v_s\right)=f\left(e_s\right)+f\left(e_{s+1}\right)+\frac{\mathrm{deg}\left(v_s\right)}{2}\left(m+1\right)$ 。对于任意的$i\in \left\{1,2,\cdots ,k\right\}$ ，如果$i$ 是偶数，假设$i=2j$ ，那么

$\begin{array}{c}{\phi }_f\left(v_i\right)\equiv f\left(e_{2j}\right)+f\left(e_{2j+1}\right)\\ \equiv f\left(e_{2j}\right)+f\left(e_{k+2-(k+1-2j)}\right)\\ \equiv f\left(e_{2j}\right)+f\left(e_{k+2-2(s-j)}\right)\\ \equiv j+m+1-\left(s-j\right)\\ \equiv m+1-s+i\left(\mathrm{mod}m+1\right)\end{array}$

如果$i$ 是奇数，假设$i=2j+1$ ，那么

$\begin{array}{c}{\phi }_f\left(v_i\right)\equiv f\left(e_{2j+1}\right)+f\left(e_{2j+2}\right)\\ \equiv f\left(e_{k+2-2(s-j)}\right)+f\left(e_{2(j+1)}\right)\\ \equiv m+1-\left(s-j\right)+j+1\\ \equiv m+1-s+i\left(\mathrm{mod}m+1\right)\end{array}$

对于$v_0$ 和$v_{k+1}$ ，${\phi }_f\left(v_0\right)=f\left(e_1\right)+\frac{\mathrm{deg}\left(v_0\right)-1}{2}\left(m+1\right)\equiv m+1-s\left(\mathrm{mod}m+1\right)$ ， ${\phi }_f\left(v_{k+1}\right)=f\left(e_{k+1}\right)+\frac{\mathrm{deg}\left(v_{k+1}\right)-1}{2}\equiv s\left(\mathrm{mod}m+1\right)$ 。

我们综合起来看，对于$i=0,1,\cdots ,k+1$ ，顶点$v_i$ 的标号${\phi }_f\left(v_i\right)\equiv m+1-s+i\left(\mathrm{mod}m+1\right)$ 并且 $m+1-s+i\ge m+1-s>m-s$ 。我们发现${\phi }_f\left(v_s\right)\equiv {\phi }_f\left(v\right)\equiv 0\left(\mathrm{mod}m+1\right)$ ，但是${\phi }_f\left(v_s\right)=\frac{\mathrm{deg}\left(v_s\right)+2}{2}\left(m+1\right)>$

$m+1={\phi }_f\left(v\right)$ 。所以在标号$f$ 下，$T+v_{s}v$ 的顶点的标号是两两不同的。因此，$T+v_{s}v$ 是反魔幻的。

定理5. 设$T$ 是一个树图，$v$ 是一个孤立点，$V_{even}\left(T\right)$ 诱导出路径$P=\left(v_1,v_2,\cdots ,v_k\right)$ ，$\left|V_{even}\left(T\right)\right|=k$ 是偶

数且$\mathrm{deg}\left(v_{s-1}\right)\ne \mathrm{deg}\left(v_{k+1}\right)+1$ ，则$T+v_{s}v$ 是反魔幻的，其中$s=\frac{k}{2}+1$ 。

证明：首先对于路径$P_0=\left(v_0,v_1,\cdots ,v_k,v_{k+1}\right)$ 中的边$e_i$ 我们的标号为$f\left(e_{2j}\right)=j$ ，$f\left(e_{k+1-2j}\right)=m-j$ ，$f\left(e_{k+1}\right)=m$ ，其中$j=1,2,\cdots ,s-1$ 。对于边$v_{s}v$ 进行标号$f\left(v_{s}v\right)=m+1$ 。那么顶点$v$ 的标号${\phi }_f\left(v\right)\equiv 1\left(\mathrm{mod}m\right)$ 。

对于$T-E\left(P_0\right)$ ，也就是${\displaystyle \underset{i=0}{\overset{k+1}{\cup }}\left(T_i,v_i\right)}$ 的边，用$\left[s,m-s\right]$ 区间内的整数进行标号。对于$i=0,1,\cdots ,k+1$ ，与

定理4相同，我们将$\left(T_i,v_i\right)$ 看作以$v_i$ 为根的有向树，$v_i$ 有偶数条出边，除$v_i$ 外的所有顶点都只有一条进边，偶数条出边。对于$\left(T_i,v_i\right)$ 中的任意顶点$u$ ，如果$u$ 的出边中存在边被标号为$t$ ，那么$u$ 的出边中也会有一条边被标号为$m-t$ 。

这样对于$\left(T_i,v_i\right)$ 中的任意除$v_i$ 之外的顶点$x$ 的标号${\phi }_f\left(x\right)\equiv f\left(e\right)\left(\mathrm{mod}m\right)$ ，其中$e$ 是顶点$x$ 的进边且$f\left(e\right)\in \left[s,m-s\right]$ 。

对于任意的$i\in \left\{1,2,\cdots ,s-1,s+1,\cdots ,k\right\}$ ，顶点$v_i$ 的标号${\phi }_f\left(v_i\right)=f\left(e_i\right)+f\left(e_{i+1}\right)+\frac{\mathrm{deg}\left(v_i\right)-2}{2}m$ ， ${\phi }_f\left(v_s\right)=f\left(e_s\right)+f\left(e_{s+1}\right)+\frac{\mathrm{deg}\left(v_s\right)}{2}m$ 。对于任意的$i\in \left\{1,2,\cdots ,k\right\}$ ，如果$i$ 是偶数，假设$i=2j$ ，那么

$\begin{array}{c}{\phi }_f\left(v_i\right)\equiv f\left(e_{2j}\right)+f\left(e_{2j+1}\right)\\ \equiv f\left(e_{2j}\right)+f\left(e_{k+1-(k-2j)}\right)\\ \equiv f\left(e_{2j}\right)+f\left(e_{k+1-2(s-1-j)}\right)\\ \equiv j+m-\left(s-1-j\right)\\ \equiv m+1-s+i\left(\mathrm{mod}m\right)\end{array}$

如果$i$ 是奇数，假设$i=2j+1$ ，那么

$\begin{array}{c}{\phi }_f\left(v_i\right)\equiv f\left(e_{2j+1}\right)+f\left(e_{2j+2}\right)\\ \equiv f\left(e_{k+1-2(s-1-j)}\right)+f\left(e_{2(j+1)}\right)\\ \equiv m-\left(s-1-j\right)+j+1\\ \equiv m+1-s+i\left(\mathrm{mod}m\right)\end{array}$

对于$v_0$ 和$v_{k+1}$ ，${\phi }_f\left(v_0\right)=f\left(e_1\right)+\frac{\mathrm{deg}\left(v_0\right)-1}{2}m\equiv m+1-s\left(\mathrm{mod}m\right)$ ， ${\phi }_f\left(v_{k+1}\right)=f\left(e_{k+1}\right)+\frac{\mathrm{deg}\left(v_{k+1}\right)-1}{2}m\equiv 0\left(\mathrm{mod}m\right)$ 。

对于$i=0,1,\cdots ,k$ ，$m+1-s+i>m-s$ 。我们发现${\phi }_f\left(v_s\right)\equiv {\phi }_f\left(v\right)\equiv 1\left(\mathrm{mod}m\right)$ ，

${\phi }_f\left(v_{s-1}\right)\equiv {\phi }_f\left(v_{k+1}\right)\equiv 0\left(\mathrm{mod}m\right)$ ，但是${\phi }_f\left(v_s\right)=\frac{\mathrm{deg}\left(v_s\right)+2}{2}m+1>m+1={\phi }_f\left(v\right)$ ，

${\phi }_f\left(v_{s-1}\right)=\frac{\mathrm{deg}\left(v_{s-1}\right)}{2}m\ne \frac{\mathrm{deg}\left(v_{k+1}\right)+1}{2}m={\phi }_f\left(v_{k+1}\right)$ 当且仅当$\mathrm{deg}\left(v_{s-1}\right)\ne \mathrm{deg}\left(v_{k+1}\right)+1$ 。所以在标号$f$ 下，

$T+v_{s}v$ 的顶点的标号是两两不同的。因此，$T+v_{s}v$ 是反魔幻的。

推论6. 设$T$ 是一个树图，$v$ 是一个孤立点，$V_2\left(T\right)$ 诱导出路径$P=\left(v_1,v_2,\cdots ,v_k\right)$ 且其他顶点的度都是

奇数，那么$T+v_{s}v$ 是反魔幻的，其中$s=\lceil \frac{k+1}{2}\rceil$ ，$k=\left|V_2\left(T\right)\right|$ 。

证明：如果$k$ 是奇数，由定理4可知，$T+v_{s}v$ 是反魔幻的。如果$k$ 是偶数且路径$P_0=\left(v_0,v_1,\cdots ,v_k,v_{k+1}\right)$ 的两个端点中存在叶子节点，则将那个叶子节点记为$P_0$ 中的顶点$v_{k+1}$ ，那么$\mathrm{deg}\left(v_{s-1}\right)=2\ne \mathrm{deg}\left(v_{k+1}\right)+1$ ，由定理5可知，$T+v_{s}v$ 是反魔幻的。

如果$k$ 是偶数且$v_0$ 和$v_{k+1}$ 都是叶子节点，则$T$ 实际上是一个路图，也就是$P_0$ 。此时$T+v_{s}v$ 实际上是一个毛毛虫图，由引理3，毛毛虫图是反魔幻图，因此$T+v_{s}v$ 是反魔幻图。

在推论6的证明中，在$k$ 是偶数且$v_0$ 和$v_{k+1}$ 都是叶子节点的情况下，我们也可以通过找到反魔幻标号证明$T+v_{s}v$ 是反魔幻图。那么我们只需要对$P_0$ 中的边$e_i$ 以及边$v_{s}v$ 进行标号。令$f\left(v_{s}v\right)=1$ ，则${\phi }_f\left(v\right)=1$ 。对于$i=1,2,\cdots ,k+1$ ，令$f\left(e_i\right)=i+1$ 。那么对于$i=1,2,\cdots ,s-1,s+1,\cdots ,k$ ，顶点$v_i$ 的标号${\phi }_f\left(v_i\right)=2i+3$ 是奇数，其中$k\ge 2$ 。${\phi }_f\left(v_0\right)=2$ ，${\phi }_f\left(v_{k+1}\right)=k+2$ ，${\phi }_f\left(v_s\right)=2s+4=k+6$ 是偶数。此时，在标号$f$ 下，$T+v_{s}v$ 的顶点的标号也是互不相同的，$T+v_{s}v$ 是反魔幻的。

3. 示例

例6. 在图1所示的树图$T_1$ 中，$V_{even}\left(T_1\right)=\left\{v_1,v_2,v_3\right\}$ 可诱导出路径，$v$ 是不属于$T_1$ 的新的顶点。在此树图中取$P_0=\left(v_0,v_1,v_2,v_3,v_4\right)$ ，$T_1+v_{2}v$ 反魔幻的，其反魔幻标号及各顶点的标号如图2所示。

Figure 1. $T_1$

图1. $T_1$

Figure 2. Anti-magic labeling of $T_1+v_{2}v$

图2. $T_1+v_{2}v$ 的反魔幻标号

例7. 在图3所示的树图$T_2$ 中，$V_2\left(T_2\right)=\left\{v_1,v_2\right\}$ 可诱导出路径且其它顶点的度数都是奇数，$v$ 是不属于$T_2$ 的新的顶点。在此树图中取$P_0=\left(v_0,v_1,v_2,v_3\right)$ ，那么$T_2+v_{2}v$ 是反魔幻的，其反魔幻标号及各顶点的标号如图4所示。

Figure 3. $T_2$

图3. $T_2$

Figure 4. Anti-magic labeling of $T_2+v_{2}v$

图4. $T_2+v_{2}v$ 的反魔幻标号

Figure 5. Anti-magic labeling of $T_3+v_{2}v$

图5. $T_3+v_{2}v$ 的反魔幻标号

例8. 若树图$T_3$ 是一条路径$P_0=\left(v_0,v_1,v_2,v_3\right)$ ，则$V_2\left(T_3\right)=\left\{v_1,v_2\right\}$ 可诱导出路径且$v_0$ 和$v_3$ 都是叶子节点。$v$ 是不属于$T_3$ 的新的顶点。那么树图$T_3+v_{2}v$ 是反魔幻的，其反魔幻标号及各顶点的标号如图5所示。