非边幻和图的若干定理及证明

Some Theorems and Proofs of Non-Edge-Magic Total Labeling Graphs

摘要

若G(p,q)的点边标号一一映射到\left\{\mathrm{1,2},\dots ,p+q\right\},使得任意边与其关联顶点的标号值之和为一个常数，这种标号被称之为边幻和全标号。本文设计了一种算法得到了9个点以内所有简单无向连通图中的非边幻和图,发现其中一些图具有某种相同的特征,因此定义了新的图运算符K_n⊳C_m和K_n∆S_m来刻画这两类联图，通过引入西顿序列，证明了在特定条件下，两类联图为非边幻和图。

Abstract

If the labeling values of edges and vertices for a graph G(p,q) are mapped one by one to {1,2，…,p+q}, the sum of the labeling values for the edge and its incident vertices equals to a constant, and this labeling is called edge-magic total labeling. In this paper, an algorithm is designed to find all non-edge-magic total labeling graphs of all simple undirected connected graphs within 9 vertices. And we also find that some of the graphs have the same characteristics, thus define the new graph s operational characters K_n⊳C_m and K_n∆S_m to depict them. Finally, by introducing the Sidon sequence, it is proved that two types of composite graphs are non-edge-magic total labeling graphs under certain conditions.

Graphical abstract

关键词

边幻和全标号 / 非边幻和图 / 算法 / 联图

Key words

edge-magic total labeling / non-edge-magic total labeling graphs / algorithm / composite graphs

0　 引 言

在图标号发展的50年里，陆续出现了一系列图标号方法，其中边幻和全标号的研究较为广泛,它在编码理论、X射线晶体学、数据库管理等领域^[1,2,3]都有应用。

Shiu等^[4]证明了：对于n\ge \mathrm{2}的m{K}_{n,n}，当且仅当n是偶数或m和n都是奇数时，具有超级边幻和全标号；fans具有边幻和全标号^[5,6,7]。

图是否具有边幻和标号的问题也是备受关注的研究热点之一，然而这方面的研究成果仍相对较少。Craft等于1999年在文献[8]中提出并证明了当且仅当r为奇数且p\equiv \mathrm{4}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{8})时，r-正则图为非边幻和图；Chen于2001年在文献[9]中证明了n{K}_{\mathrm{2}}+n{K}_{\mathrm{2}}无超级边幻和全标号;文献[10]已证明：当且仅当q为偶数且p+q\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})时，图n{P}_n为非边幻和图;文献[8]证明了当n\ge \mathrm{7}时，所有的K_n均为非边幻和图。

本文利用算法并结合文献[11]中给出的非同构图生成方法，对有限点的图进行边幻和性判定，并得出其中所有的非边幻和图，通过观察与分析找到具有某种规律的图全为非边幻和图。最后引入西顿序列，证明了当n\ge \mathrm{8}且m、n满足一定关系时，K_n⊳C_m和K_n∆S_m为非边幻和图。

1　 预备知识

本文涉及到的图G(p,q)为简单无向连通图，其中p表示顶点数，q表示边数;星图S_n的定义为n-1个叶子结点连接到1个中心点，其他未定义的术语和符号参考文献[12]。

定义1^[13] 图G(p,q)存在双射f:V(G)\bigcup E(G)\to [\mathrm{1},p+q]，使对G的任意一条边uv，总有f（u）+f（v）+f（uv）=k，则称f为图G(p,q)的一个边幻和全标号(edge-magic total labeling，EMTL)，k为幻和常数。若f（V（G））\to [\mathrm{1},p]，则称为图G的一个超级边幻和全标号(super edge-magic total labeling，SEMTL)。

定义2 将圈图C_m的任意一条边并接到K_n的任意一条边后得到的联图，记为K_n⊳C_m，其顶点

V（K_n⊳C_m）=V（K_n）\bigcup V（C_m）\backslash \mathrm{2}v

即

\left|V（K_n⊳C_m）\right|=\left|V（K_n）\right|+\left|V（C_m）\right|-\mathrm{2}

其边

E（K_n⊳C_m）=E（K_n）\bigcup E（C_m）\backslash e

即

\left|E（K_n⊳C_m）\right|=\left|E（K_n）\right|+\left|E（C_m）\right|-\mathrm{1}K_n⊳C_m示例如图1(a)所示。

定义3 将星图S_m的中心点并接到K_n的任意一顶点之后得到的联图，记为K_n∆S_m，其顶点

V（K_n∆S_m）=V（K_n）\bigcup V（S_m）\backslash v

即

\left|V（K_n∆S_m）\right|=\left|V（K_n）\right|+\left|V（S_m）\right|-\mathrm{1}

其边

E（K_n∆S_m）=E（K_n）\bigcup E（S_m）

K_n∆S_m示例如图1(b)所示。

定义4 对于图G(p,q),设三元组（a,b,c）表示图中任意相邻顶点及其边的标号，存在整数k，满足a+b+c=k，a,b,c\in [\mathrm{1},p+q]，p+q+\mathrm{3}\le k\le \mathrm{2}p+\mathrm{2}q，则称三元向量(a,b,c)的取值空间为图G(p,q)的EMTL解空间，记为\phi (p,q,k)。如表1所示。

由定义1和定义4知，如下引理显然成立。

引理1 如果G(p,q)是EMTL图，设（a,b,c）为满足EMTL的相邻点和边标号三元组，则\forall (a,b,c)\in \phi (p,q,k)。

引理2 如果G(p,q)为非边幻和图（no⁃edge⁃magic⁃total⁃labeling，NEMTL），设（a,b,c）为图G（p,q）中相邻点和边标号三元组，则不存在整数k和q组(a,b,c)

\in \phi (p,q,k)，满足a+b+c=k，a,b,c\in [\mathrm{1},p+q]，p+q+\mathrm{3}\le k\le \mathrm{2}p+\mathrm{2}q。

2　 EMTL算法

2.1　基本计算

由定义1可知

\sum _{uv\in E}(f（u）+f（v）+f(uv))=qk(1)

由于每个边标号只相加一次，点标号需要相加d（v_i）-\mathrm{1}次，故（1）式可化简为：

qk=C+\sum _{i=\mathrm{1}}^p（d（v_i）-\mathrm{1}）f(v_i)（2）

其中d(v_i)表示顶点v_i的度，常数C=\sum _{j=\mathrm{1}}^{p+q}j=\frac{（p+q）（p+q+\mathrm{1}）}{\mathrm{2}}。

为遍历图G（p,q）的解空间，需对边进行标号，故设边系数均为0，由此可得

qk=C+\sum _{i=\mathrm{1}}^p（d（v_i）-\mathrm{1}）f(v_i)+\mathrm{0}\cdot \sum _{j=\mathrm{1}}^{q}f（e_j）(3)

2.2　算法思想

1） 计算图G（p,q）的度序列、常数C和点系数(d(v_i)-\mathrm{1})；

2） 初始化f(v_i)： f(v_i）\in [\mathrm{1},p]且标号值从小到大排列；

3） 如果存在正整数k使（3）式成立，则使用分配函数Allocation分配点和边的标号，若不成立，则对点系数与边系数0组成的序列Coe做一次全排列。

4） 若分配函数Allocation返回true，则表示该图存在EMTL，算法结束；若返回false，则继续对Coe做一次全排列；

5） 若Allocation返回true或全排列结束，则终止算法；若全排列结束时Allocation返回false，则表示该图为NEMTL图。

EMTL算法如算法1。

Allocation (n,start,matrix)函数用来分配点、边的标号。其思想为利用递归算法来分配标号，需遵守以下原则：

1） 若层数n超过了矩阵的行数，则分配成功，返回true。

2） 若当前层顶点元素与已填入元素产生冲突，则退回上一层，并且start++；

3） 若顶点元素已被分配，则start++。

4） 若当前层的元素取值start超过当前层元素的个数，则退回上一层。

5） 如第一层的元素取值超过第一层元素个数，则退出，分配失败，返回false。

Allocation (n,start,matrix)函数描述如下:

引理3 EMTL算法搜索图G（p,q）的EMTL解空间\phi (p,q,k)，如果有解，则图G（p,q）为EMTL图；否则为NEMTL图。

证 根据引理1和引理2，引理3显然成立。

例1图2为图集G(8,10)中一个EMTL和NEMTL图，表2为图集G(8,10)的解空间。

表2中加粗加下划线的标号组合为图2(a)的解，图2(b)在\phi (\mathrm{8,10},k)中无解，为NEMTL图。

3　 有关NEMTL图的定理及证明

定理1 当\mathrm{7}\le n\le \mathrm{9}时，图K_n\backslash e为NEMTL图。

证 1) 图K_n\backslash e，当\mathrm{7}\le n\le \mathrm{9}时，在其对应的解空间\phi （\mathrm{7,20},k）\mathrm{、}\phi (\mathrm{8,27},k)、\phi (\mathrm{9,35},k)上执行EMTL算法，得出该类图G均为NEMTL,其结果如表3所示。

2)K_n\backslash e的示例图如图3所示

猜测1 当n\ge \mathrm{10}时，图K_n\backslash e为NEMTL图。

定理2 当\mathrm{7}\le p\le \mathrm{9}，q\ge \frac{p(p-\mathrm{1})}{\mathrm{2}}-\mathrm{2}(p-\mathrm{6})

+\mathrm{1}时，图G（p,q）均为NEMTL图。

证 1) 图G（p,q）,当q\ge \frac{p(p-\mathrm{1}）}{\mathrm{2}}-\mathrm{2}（p-\mathrm{6}）+\mathrm{1}时，在其对应的解空间\phi （\mathrm{7,20},k），\phi (\mathrm{7,21},k),

…,\phi (\mathrm{9,36},k)上执行EMTL判定算法，得出该类图不存在EMTL,其结果如表4所示，故当q\ge \frac{p(p-\mathrm{1})}{\mathrm{2}}-\mathrm{2}(p-\mathrm{6})+\mathrm{1}且\mathrm{7}\le p\le \mathrm{9}时，图G（p,q）均为NEMTL图成立。

2) 图命名规则如下:G(p，q)-num，其中p为点数，q为边数，num表示当前(p,q)图集下的第num个图。图4给出该图集中当p=\mathrm{7}，p=\mathrm{8}时除K_p和K_p\backslash e外的全部图。由于此图集中当p=\mathrm{9}时，图的数量较多，故仅给出部分示例，如图5所示。

证毕。

猜测2 当p\ge \mathrm{10}，q\ge \frac{p(p-\mathrm{1})}{\mathrm{2}}-\mathrm{2}(p-\mathrm{6})+\mathrm{1}时，图G（p,q）为NEMTL图。

定理3、4的预备知识：

1) 对于图G(p,q),若其存在EMTL，边幻和常数为k,且包含一个具有n个顶点的完全子图H,u_{\mathrm{1}},u_{\mathrm{2}},…,u_n分别为H的n个顶点，a_i=f(u_i),则

f（u_i{u}_j）=k-a_i-a_j，

f（u_k{u}_l）=k-a_k-a_l，

f（u_i{u}_j）\ne f（u_k{u}_l），

故a_i+a_j\ne a_k+a_l,即H中的任意两顶点之和均不相同。

2) 若序列A=（a_{\mathrm{1}},a_{\mathrm{2}},\dots ,a_n）,且满足以下性质：

① ，

② 如果a_i，a_j，a_k，a_l为A中四个不同的元素，则a_i+a_j\ne a_k+a_l，A叫做西顿(Sidon)序列^[14]。

若\sigma (A)表示Sidon序列的大小，定义：

\sigma （A）=a_n-a_{\mathrm{1}}+\mathrm{1},

\begin{array}{l}\rho （A）=a_n+a_{n-\mathrm{1}}-a_{\mathrm{2}}-a_{\mathrm{1}}+\mathrm{1}=\\ \sigma （A）+a_{n-\mathrm{1}}-a_{\mathrm{2}}，\end{array}

{\sigma }^{\mathrm{*}}（A）=\mathrm{m}\mathrm{i}\mathrm{n}\sigma （A）,{\rho }^{\mathrm{*}}(A)=\mathrm{m}\mathrm{i}\mathrm{n}\rho (A)

3) 对于图G(p,q),若其存在EMTL，边幻和常数为k,且包含一个具有n个顶点的完全子图H,u_{\mathrm{1}},u_{\mathrm{2}},…,u_n分别为H的n个顶点，a_i=f(u_i)。假定,则A=（a_{\mathrm{1}},a_{\mathrm{2}},\dots ,a_n）为一个长度为n的Sidon序列。

f（u_n{u}_{n-\mathrm{1}}）=k-a_n-a_{n-\mathrm{1}}

又f（u_n{u}_{n-\mathrm{1}}）为标号

k-a_n-a_{n-\mathrm{1}}\ge \mathrm{1}（4）

同理

f（u_{\mathrm{2}}{u}_{\mathrm{1}}）=k-a_{\mathrm{2}}-a_{\mathrm{1}}

又f（u_{\mathrm{2}}{u}_{\mathrm{1}}）为标号

k-a_{\mathrm{2}}-a_{\mathrm{1}}\le p+q（5）

由（4）和（5）式得

\begin{array}{c}p+q\ge a_n+a_{n-\mathrm{1}}-a_{\mathrm{2}}-a_{\mathrm{1}}+\mathrm{1}=\\ \rho （A）\ge {\rho }^{\mathrm{*}}（A）\end{array}（6）

从而得出,图G(p,q)若包含一个具有n个顶点的完全子图，且其具有EMTL,则p+q至少为{\rho }^{\mathrm{*}}（n），即：当时，图G为NEMTL图。

4) 文献[14]已证明：

当n\ge \mathrm{4}时,{\rho }^{\mathrm{*}}（A）\ge \mathrm{2}{\sigma }^{\mathrm{*}}(n-\mathrm{1}) （7）

当n\ge \mathrm{7}时，{\sigma }^{\mathrm{*}}(n)\ge \mathrm{4}+C_{n-\mathrm{1}}^{\mathrm{2}} （8）

定理3 当n\ge \mathrm{8}，m\le \frac{\mathrm{17}}{\mathrm{2}}+\frac{\mathrm{1}}{\mathrm{4}}(n^{\mathrm{2}}-\mathrm{11}n),且m,n均为正整数时，K_n⊳C_m为NEMTL图。

证 1) K_n⊳C_m如图1(a)。设K_n的顶点集为\left\{u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n\right\},C_m的顶点集为\left\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_m\right\}。当

时，K_n⊳C_m为NEMTL图。即

结合（7）和（8）式知：

当n\ge \mathrm{4}时,

当n\ge \mathrm{8}时，

化简得：)。故当n\ge \mathrm{8}，),且m,n均为正整数时,K_n⊳C_m为NEMTL图。

2) 图6中的零散点表示m,n的解，C_m为圈图，故m\ge \mathrm{3}时，函数图像才有意义；当n\ge \mathrm{13}时略。

3) 图7为K_n⊳C_m满足定理3的部分NEMTL图示例。

证毕。

定理4 当n\ge \mathrm{8}，时，K_n∆S_m为NEMTL图。

证 1) K_n∆S_m如图1(b)。设K_n的顶点集为\left\{u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n\right\},S_m的顶点集为\left\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_m\right\}。当

时，K_n∆S_m为NEMTL图。即

又结合（7）和（8）式知：

当n\ge \mathrm{4}时,

当n\ge \mathrm{8}时，

化简得：)。故当n\ge \mathrm{8}，时，K_n∆S_m为NEMTL图成立。

2) 图8中的零散点表示m,n的可能取值，S_m为星图，故m\ge \mathrm{2}时，函数图像才有意义；当n\ge \mathrm{13}时略。

3) 图9为K_n∆S_m满足定理3的部分NEMTL图示例。

证毕。

从定理3和4可知，当n\ge \mathrm{8}时，联图才满足NEMTL的条件表达式，通过对9个点以内的所有图执行EMTL算法，得到了这两种联图当时，部分图也为NEMTL，如图10所示。由于其并没有具体规律，故不用定理列出。

4　 结 语

本文设计了一种EMTL算法，得到了9个点内所有NEMTL图。通过分析得到了定理1和定理2，同时提出猜测1和猜测2，并发现大部分NEMTL图均为对称图形。最后，通过引入Sidon序列，证明了当n和m满足某些条件时，联图K_n⊳C_m和K_n∆S_m为非边幻和图，并对时，Sidon序列无法证明的NEMTL联图做了补充。

参考文献

[1] BLOOM G S, GOLOMB S W. Applications of numbered undirected graphs[J]. Proceedings of the IEEE, 1977, 65(4): 562-570. DOI: 10.1109/PROC.1977.10517 .

[2] BLOOM G S, GOLOMB S W . Numbered complete graphs, rulers unusual, and assorted applications[C]//Theory and Applications of Graphs（LNM 642）. Berlin：Springer, 1978: 53-65. DOI: 10.1007/BFb0070364 .

[3] ARKUT I C, ARKUT R C, BASAK A. Topology constrained label switching for multicast routing[C]//Proceedings of the 8th IEEE Symposium on Computers and Communications. Washington D C:IEEE Computer Society, 2003: 453-459. DOI: 10.1109/ISCC.2003.1214160 .

[4] SHIU W C, LAM P C B, CHENG H L. Supermagic labeling of an s-duplicate of K n , n [J]. Congressus Numerantium, 2000,146:119-124.

[5] LIN Y, MILLER M, SIMANJUNTAK R. Edge-magic total labelings of wheels, fans and friendship graphs[J]. Bulletin of the ICA, 2002, 35: 89-98.

[6] FIGUEROA-CENTENO R M, ICHISHIMA R, MUNTANER-BATLE F A. The place of super edge-magic labelings among other classes of labelings [J]. Discrete Mathematics, 2001, 231(1-3): 153-168. DOI: 10.1016/S0012-365X(00)00314-9 .

[7] FIGUEROA-CENTENO R M, ICHISHIMA R, MUNTANER-BATLE F A. On super edge-magic graphs [J]. Ars Comb, 2002, 64: 81-95.

[8] CRAFT D, TESAR E H. On a question by Erdős about edge-magic graphs [J]. Discrete Mathematics, 1999, 207(1-3): 271-276. DOI: 10.1016/S0012-365X(99)00110-7 .

[9] CHEN Z B. On super edge-magic graphs [J]. Journal of Combinatorial Mathematics and Combinatorial Computing, 2001, 38: 55-64.

[10] RINGEL G, LLADO A S, SERRA O. Another tree conjecture[J]. Bull Inst Combin Appl, 1996, 18: 83-85.

[11] MCKAY B D, PIPERNO A. Practical graph isomorphism, Ⅱ[J]. Journal of Symbolic Computation, 2014, 60: 94-112. DOI： 10.1016/j.jsc.2013.09.003 .

[12] GALLIAN J A. A survey: Recent results, conjectures, and open problems in labeling graphs[J]. Journal of Graph Theory, 1989, 13(4): 491-504. DOI： 10.1002/jgt.3190130410 .

[13] KOTZIG A, ROSA A. Magic valuations of finite graphs[J]. Canadian Mathematical Bulletin, 1970, 13(4): 451-461. DOI： 10.4153/CMB-1970-084-1 .

[14] MARR A M, WALLIS W D. Magic Graphs [M].2nd Ed. Boston：Birkhäuser, 2012.

基金资助

国家自然科学基金(11461038)