树的反魔幻标号

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.