随机图的邻点和可约边标号算法

Adjacent Vertex Sum Reducible Edge Labeling Algorithm of the Random Graph

摘要

如果对于一个点数为p，边数为q的图G(p,q)，存在映射f:E(G)\to \{\mathrm{1,2},\dots ,q\}，并且对于任意两个同度相邻点u,v存在\mathrm{S}\mathrm{u}\mathrm{m}(u)=\mathrm{S}\mathrm{u}\mathrm{m}(v)，其中\mathrm{S}\mathrm{u}\mathrm{m}(u)=\sum _{uv\in E(G)}f(uv)，称f为图的邻点和可约边标号。在已有的点魔幻边标号和点可约边染色研究的基础上，结合实际应用，提出了邻点和可约边标号的新概念，并设计了邻点和可约边标号（adjacent vertex sum reducible edge labeling，AVSREL）算法。算法通过循环迭代寻优的方式，对图进行标号，得到了10个点内所有非同构图的标号结果，经过结果分析总结出若干定理并加以证明。

Abstract

For a graph G(p,q) with the number of vertices p and the number of edges q, there is a mapping f:E(G)\to\{\mathrm{1,2},\dots ,q\}, and for any two adjacent vertices of the same degree u,v exists \mathrm{S}\mathrm{u}\mathrm{m}(u)=\mathrm{S}\mathrm{u}\mathrm{m}(v), where \mathrm{S}\mathrm{u}\mathrm{m}(u)=\sum _{uv\in E(G)}f(uv), and f is called adjacent vertex sum reducible edge labeling. Based on the existing research on vertex-magic edge labeling and vertex reducible edge coloring, a new concept of adjacent vertex sum reducible edge labeling is proposed in this paper. And based on the definition of this new concept, the algorithm for adjacent vertex sum reducible edge labeling (AVSREL algorithm for short) is designed. The algorithm adopts the loop iteration for labeling the graphs, and the labeling results of all non-isomorphic graphs within 10 points are obtained. Analyzing the results, several theorems are summarized and proved.

Graphical abstract

关键词

图 / 点魔幻边标号 / 点可约边染色 / 邻点和可约边标号算法

Key words

graphs / vertex-magic edge labeling / vertex reducible edge coloring / adjacent vertex sum reducible edge labeling algorithm

0　 引 言

1967年，Rosa等^［1］提出“每一棵树都是优美的”的猜想，图标号的概念由此而来。在之后的几十年中，研究者们展开了对图标号问题的研究与探讨。1970年，Kotzig等^［2］提出了关于图的边幻和全标号概念，并且提出猜想：每一棵树都有一个边魔幻全标号。1999年，MacDougall等^［3］提出了顶点魔幻全标号。在此基础上，又提出了顶点魔幻边标号，它的要求是每个点的关联边标号和要保证相同。1997年，Burris^［4］提出了点可区别边染色的概念。2009年，文献［5］在可区别染色的理论基础上，提出了可约染色的概念。2013年Flandrin^［6］提出邻和可区别边染色猜想。2015年，Pilśniak等^［7］又提出了邻和可区别全染色的概念。

本文在这些学者研究的基础上，提出邻点和可约边标号新概念。利用文献［8］的方法生成了10个点以内的所有非同构图集。设计了邻点和可约边标号的算法，对随机图进行研究，得到实验结果后对结果进行分析，并得到一些相关的定理及证明。

1　 基本概念

本文中的图均为p个顶点，q条边的无向简单连通图G(p,q)。

定义1 对于G(p,q)，存在一个映射f：E(G)\to \{\mathrm{1,2},\dots ,q\}，\mathrm{S}\mathrm{u}\mathrm{m}(u)=\sum _{uv\in E(G)}f(uv)。令d(u)为点u的度，如果d(u)=d(v)，那么\mathrm{S}\mathrm{u}\mathrm{m}(u)=\mathrm{S}\mathrm{u}\mathrm{m}(v)。则称f为图的邻点和可约边标号（adjacent vertex sum reducible edge labeling，AVSREL）。

一个图存在AVSREL，则称其为AVSREL图，否则称其为非AVSREL图。

定义2 设C_n^H表示阶数为n的圈图的每个顶点都连接一个子图而形成的联图，其中，H=\{H_i|i=\mathrm{1},\mathrm{2,3},\dots ,n\}，|V(C_{\mathrm{3}}^H)|=|V(C_{\mathrm{3}})|+|{\displaystyle \sum _{i=\mathrm{1}}^n}V(H_i)|-n，|E(C_{\mathrm{3}}^H)|=|E(C_{\mathrm{3}})|+|{\displaystyle \sum _{i=\mathrm{1}}^n}E(H_i)|。图1为圈图C_{\mathrm{3}}的3个顶点分别连接3个星图形成的联图。

2　 AVSREL算法

根据邻点和可约边标号的定义，设计了AVSREL算法，以循环迭代寻优的方式对图进行边标号。

2.1　基本原理

1）　预处理函数Pretreatment（）

① 输入图的邻接矩阵；

② 计算出每个点的度，图G(p,q)的边数q。

③ 得到相邻的同度点的集合为list1。

2）　调整函数isSurpassTwo（）

① 初始化邻接矩阵，此时相邻的同度点标号和相同。

② 设置判断是否需要调整的函数isSurpassTwo（），判断相邻同度点标号和是否差2。

③ 从右上角三角形开始，从左到右，从上到下依次进行调整，每次增加1。

④ 若得到相邻的同度点标号和符合函数isSurpassTwo（），则回退，调整下一个，循环第③步。

3）　平衡函数isBalance（）

判断相邻的同度点标号和是否相同且标号数连续，若是则返回TRUE，否则返回FALSE；

4）　输出函数Output（）

① 判断边的标号数是否达到图G(p,q)的边数q；

② 若达到，且满足平衡函数isBalance（），则符合邻点和可约边标号；若其中一个条件不满足，则不符合。

③ 输出符合的标号矩阵。

2.2　邻点和可约边标号算法结果

表1展示了3个点到6个点不同边数的图总数中AVSREL图数的情况。由表1可知，随着边数的增加，AVSREL图的个数整体先增加后减少。

图2中展示了7个点到10个点不同边数的图总数中AVSREL图数的情况。

图3给出了7个点到10个点不同边数的图中， AVSREL图占各个边总图数量的比例。可以看到比例先上升后下降。

图4给出部分图的邻点和可约边标号示例。

3　 定理及证明

定理1P_n是具有n(n\ge \mathrm{2})个顶点的路图，当n\ge \mathrm{4}时，P_n为非AVSREL图。

定理2 阶数为n的圈图C_n为非AVSREL图。

根据邻点和可约边标号定义，定理1和定理2显然成立。

定理3 若S_m是具有m+1（m＞2）个顶点的星图，则可知S_m是AVSREL图。

证 对于S_m，除了星心之外的每个点都不相邻，因此对每条边的标号，可取E(G)\to \{\mathrm{1,2},\dots ,q\}，易知S_m是AVSREL图。

定理4 双星图S_{m,n}是AVSREL图（图5）。

证 根据双星图S_{m,n}左右两边顶点个数的情况，分以下两种情形讨论。

情形1 当m\ne n时。

可知由于m\ne n，则d(u_{\mathrm{0}})\ne d(v_{\mathrm{0}})。根据邻点和可约边标号定义，易知是AVSREL图。

情形2 当m=n时，分四种情况。

1） 当双星图m=n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})，可以得到关于f的映射

f(u_{\mathrm{0}}{v}_{\mathrm{0}})=f(u_{\mathrm{0}}{u}_m)+\mathrm{1}=\mathrm{2}m+\mathrm{1}

此时，u_{\mathrm{0}}与v_{\mathrm{0}}相邻且同度，

\mathrm{S}\mathrm{u}\mathrm{m}(d(u_{\mathrm{0}}))=\mathrm{1}+\mathrm{3}+\mathrm{6}+\mathrm{8}+\dots +\mathrm{2}i-\mathrm{1}+

\mathrm{2}i+\mathrm{2}m+\mathrm{1}=\mathrm{18}+\mathrm{4}i+\mathrm{2}m

\mathrm{S}\mathrm{u}\mathrm{m}(d(v_{\mathrm{0}}))=\mathrm{2}+\mathrm{4}+\mathrm{5}+\mathrm{7}\dots +\mathrm{2}i+\mathrm{2}i-\mathrm{1}+

\mathrm{2}m+\mathrm{1}=\mathrm{18}+\mathrm{4}i+\mathrm{2}m

因此，当双星图m=n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，S_{m,n}是AVSREL图。

2） 当双星图m=n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})，且m+\mathrm{1}\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})\mathrm{时},可以得到关于f的映射

f(u_{\mathrm{0}}{v}_{\mathrm{0}})=m+\mathrm{1}

此时，u_{\mathrm{0}}与v_{\mathrm{0}}相邻且同度。

\mathrm{S}\mathrm{u}\mathrm{m}(d(u_{\mathrm{0}}))=\mathrm{2}i-\mathrm{1}+\mathrm{2}i+\mathrm{2}i-\mathrm{1}+\dots +\mathrm{2}i+

\mathrm{1}+\mathrm{2}i+\mathrm{2}i+\mathrm{1}+\mathrm{2}i+m+\mathrm{1}=\mathrm{14}i+m+\mathrm{1}，

\mathrm{S}\mathrm{u}\mathrm{m}(d(v_{\mathrm{0}}))=\mathrm{2}i+\mathrm{2}i-\mathrm{1}+\mathrm{2}i+\dots +\mathrm{2}i-\mathrm{1}+

\mathrm{2}i+\mathrm{1}+\mathrm{2}i+\mathrm{2}i+\mathrm{1}+m+\mathrm{1}=\mathrm{14}i+m+\mathrm{1}

因此，当双星图m=n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})，且m+\mathrm{1}\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})\mathrm{时}，S_{m,n}是AVSREL图。

3） 当双星图m=n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})，且m+\mathrm{1}\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})\mathrm{时},可以得到关于f 的映射

f(u_{\mathrm{0}}{u}_i)=

f(u_{\mathrm{0}}{v}_{\mathrm{0}})=m+\mathrm{1}

此时，u_{\mathrm{0}}与v_{\mathrm{0}}相邻且同度。

\begin{array}{l}\mathrm{S}\mathrm{u}\mathrm{m}(d(u_{\mathrm{0}}))=\mathrm{2}i-\mathrm{1}+\mathrm{2}i+\mathrm{2}i-\mathrm{1}+\dots +\\ \mathrm{2}i+\mathrm{1}+\dots +\mathrm{2}i+\mathrm{1}=\mathrm{10}i+m+\mathrm{1}\end{array}

\begin{array}{l}\mathrm{S}\mathrm{u}\mathrm{m}(d(v_{\mathrm{0}}))=\mathrm{2}i+\mathrm{2}i-\mathrm{1}+\dots +\mathrm{2}i+\mathrm{1}+\mathrm{2}i+\\ \dots +\mathrm{2}i+m+\mathrm{1}=\mathrm{10}i+m+\mathrm{1}\end{array}

因此，当双星图m=n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})，且m+\mathrm{1}\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})\mathrm{时}，S_{m,n}是AVSREL图。

4）当双星图m=n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})，且m+\mathrm{1}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})或m+\mathrm{1}\equiv \mathrm{3}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})时，为非奇数，因此和m=n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时的映射相同。

定理4得证。

定理5 联图C_{\mathrm{3}}^H为AVSREL图（图6），其中H=\{\mathrm{\varnothing },S_n,S_m\}。

证 根据联图C_{\mathrm{3}}^H，H=\{\mathrm{\varnothing },S_n,S_m\}左右两边顶点个数的情况，分以下两种情形讨论。

情形1 当两个星图的顶点个数不相同时，即m\ne n，易知相邻点的度都不相同，则此时联图共有m+n+\mathrm{3}条边，将每条边标号依次为\mathrm{1,2},\mathrm{3},\dots ,m+n+\mathrm{3}。此时，边标号序列满足E(G)\to \{\mathrm{1,2},\dots ,q\}，因此，C_{\mathrm{3}}^H,H=\{\mathrm{\varnothing },S_n,S_m\}是AVSREL图。

情形2 当单圈图C_{\mathrm{3}}连接的两个星图的顶点个数相同时，即m=n\mathrm{。}

当m=n=\mathrm{1}，m=n=\mathrm{2}时，可以得到如图7所示下标号。

当m=n>\mathrm{2}\mathrm{时}，顶点数为m+n+\mathrm{3}，边数也为m+n+\mathrm{3}。可以得到关于f\mathrm{的}\mathrm{映}\mathrm{射}

f(v_{\mathrm{0}}{v}_i)=\left\{\begin{array}{ll}\mathrm{1},& i=\mathrm{1}\\ i+\mathrm{2},& i=\mathrm{2}\mathrm{或}\mathrm{3}\\ i+\mathrm{3},& i=\mathrm{4}\\ \mathrm{2}i,& \mathrm{5}\le i\le n\mathrm{a}\mathrm{n}\mathrm{d}i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{2}i-\mathrm{1},& \mathrm{5}\le i\le n\mathrm{a}\mathrm{n}\mathrm{d}i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

f(u_{\mathrm{0}}{u}_i)=\left\{\begin{array}{ll}i+\mathrm{1},& i=\mathrm{1}\mathrm{或}\mathrm{2}\\ i+\mathrm{3},& i=\mathrm{3}\\ \mathrm{2}i,& \mathrm{4}\le i\le m\mathrm{a}\mathrm{n}\mathrm{d}i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{2}i-\mathrm{1},& \mathrm{4}\le i\le m\mathrm{a}\mathrm{n}\mathrm{d}i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

当m=n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时,

\left\{\begin{array}{l}f(w_{\mathrm{1}}{w}_{\mathrm{2}})=m+n+\mathrm{3}\\ f(w_{\mathrm{2}}{w}_{\mathrm{3}})=m+n+\mathrm{3}-\mathrm{2}=m+n+\mathrm{1}\\ f(w_{\mathrm{1}}{w}_{\mathrm{3}})=m+n+\mathrm{3}-\mathrm{1}=m+n+\mathrm{2}\end{array}\right.

当m=n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，

\left\{\begin{array}{l}f(w_{\mathrm{1}}{w}_{\mathrm{2}})=m+n+\mathrm{3}\\ f(w_{\mathrm{2}}{w}_{\mathrm{3}})=m+n+\mathrm{3}-\mathrm{1}=m+n+\mathrm{2}\\ f(w_{\mathrm{1}}{w}_{\mathrm{3}})=m+n+\mathrm{3}-\mathrm{2}=m+n+\mathrm{1}\end{array}\right.

当m=n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\mathrm{时}，可知，

f(v_{\mathrm{0}}{v}_i)\to \{\mathrm{1,4},\mathrm{5,7},\mathrm{10,11,14},\dots ,\mathrm{2}i-\mathrm{1}\}f(u_{\mathrm{0}}{u}_i)\to \{\mathrm{2,3},\mathrm{6,8},\mathrm{9,12,13},\dots ,\mathrm{2}i\}

又因为m=n，所以m+n=\mathrm{2}i。且此时

f(w_{\mathrm{1}}{w}_{\mathrm{2}})=m+n+\mathrm{3}=\mathrm{2}i+\mathrm{3}

\begin{array}{l}f(w_{\mathrm{2}}{w}_{\mathrm{3}})=m+n+\mathrm{3}-\mathrm{2}=\\ m+n+\mathrm{1}=\mathrm{2}i+\mathrm{1}\end{array}

\begin{array}{l}f(w_{\mathrm{1}}{w}_{\mathrm{3}})=m+n+\mathrm{3}-\mathrm{1}=\\ m+n+\mathrm{2}=\mathrm{2}i+\mathrm{2}\end{array}

可知，所有边标号映射到E(G)\to \{\mathrm{1,2},\mathrm{3},\dots ,\mathrm{2}i+\mathrm{3}\}且连续。又因为w_{\mathrm{1}}与w_{\mathrm{3}}相邻并且度相同，此时

\begin{array}{l}\mathrm{S}\mathrm{u}\mathrm{m}(d(w_{\mathrm{1}}))=\mathrm{1}+\mathrm{4}+\mathrm{5}+\mathrm{7}+\mathrm{10}+\mathrm{11}+\\ \mathrm{14}+\dots +\mathrm{2}i-\mathrm{1}=\mathrm{52}+\mathrm{6}i+\mathrm{4}\end{array}

\begin{array}{l}\mathrm{S}\mathrm{u}\mathrm{m}(d(w_{\mathrm{3}}))=\mathrm{2}+\mathrm{3}+\mathrm{6}+\mathrm{8}+\mathrm{9}+\mathrm{12}+\\ \mathrm{13}+\dots +\mathrm{2}i=\mathrm{53}+\mathrm{6}i+\mathrm{3}=\\ \mathrm{52}+\mathrm{6}i+\mathrm{4}\end{array}

可知w_{\mathrm{1}}与w_{\mathrm{3}}标号和相同。因此，C_{\mathrm{3}}^H是AVSERL图，其中H=\{\mathrm{\varnothing },S_n,S_m\}。

同理可得，当m=n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，C_{\mathrm{3}}^H也是AVSREL图，其中H=\{\mathrm{\varnothing },S_n,S_m\}。

定理5得证。

定理6 联图C_{\mathrm{3}}^H为AVSREL图（如图8），其中H=\{S_i,S_j,S_m\}。

证 根据联图C_{\mathrm{3}}^H，H=\{S_i,S_j,S_m\}连接的三个星图的顶点个数情况，分以下三种情形。

情形1 当i\ne j\ne m时，即连接的三个星图顶点个数不相同，可知相邻点度都不相同，因此可以将边按照E(G)\to \{\mathrm{1,2},\mathrm{3},\dots ,i+j+m\}的顺序进行标号，所以C_{\mathrm{3}}^H是AVSREL图，其中H=\{S_i,S_j,S_m\}。

情形2 当i=j，但i\ne m,j\ne m时，即连接的两个星图顶点个数相同，有一个不相同时，v_{\mathrm{0}}与u_{\mathrm{0}}相邻，且度相等，可在上文m=n情形的基础上，对f(w_{\mathrm{0}}{w}_{\mathrm{1}})=i+j+\mathrm{4}，f(w_{\mathrm{0}}{w}_{\mathrm{2}})=i+j+\mathrm{5}，…，f(w_{\mathrm{0}}{w}_m)=m+i+j+\mathrm{3}。可知，此时满足所有边为连续，且标号值到最大边数m+i+j+\mathrm{3}，并且满足相邻点度相同，标号和相同，所以C_{\mathrm{3}}^H是AVSREL图，其中H=\{S_i,S_j,S_m\}。

情形3 当m=i=j时，即连接的三个星图顶点个数都相同时，此时可知v_{\mathrm{0}},u_{\mathrm{0}},w_{\mathrm{0}}两两相邻，且度相同。

当m=i=j=\mathrm{1}，m=i=j=\mathrm{2}时，分别可得如图9标号图。

当m=i=j=\mathrm{3}，m=i=j=\mathrm{4}时，分别可得如图10的标号图。

当m=i=j=\mathrm{5}，m=i=j=\mathrm{6}时，分别可得如图11的标号图。

当m=i=j\ge \mathrm{7}时，可得到如下映射

f(u_{\mathrm{0}}{u}_i)=\left\{\begin{array}{ll}\mathrm{3},& i=\mathrm{1}\\ \mathrm{4},& i=\mathrm{2}\\ \mathrm{8},& i=\mathrm{3}\\ \mathrm{11},& i=\mathrm{4}\\ \mathrm{13},& i=\mathrm{5}\\ \mathrm{17},& i=\mathrm{6}\\ \mathrm{3}i-\mathrm{1},& i\ge \mathrm{7}\end{array}\right.

f(v_{\mathrm{0}}{v}_j)=\left\{\begin{array}{ll}\mathrm{1},& j=\mathrm{1}\\ \mathrm{5},& j=\mathrm{2}\\ \mathrm{7},& j=\mathrm{3}\\ \mathrm{12},& j=\mathrm{4}\\ \mathrm{15},& j=\mathrm{5}\\ \mathrm{18},& j=\mathrm{6}\\ \mathrm{3}j,& j\gg \mathrm{7}\mathrm{a}\mathrm{n}\mathrm{d}j\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{3}j-\mathrm{2},& j\gg \mathrm{7}\mathrm{a}\mathrm{n}\mathrm{d}j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

f(w_{\mathrm{0}}{w}_m)=\left\{\begin{array}{ll}\mathrm{2},& m=\mathrm{1}\\ \mathrm{6},& m=\mathrm{2}\\ \mathrm{9},& m=\mathrm{3}\\ \mathrm{10},& m=\mathrm{4}\\ \mathrm{14},& m=\mathrm{5}\\ \mathrm{16},& m=\mathrm{6}\\ \mathrm{3}m-\mathrm{2},& m\gg \mathrm{7}\mathrm{a}\mathrm{n}\mathrm{d}m\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{3}m,& m\gg \mathrm{7}\mathrm{a}\mathrm{n}\mathrm{d}m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

f(v_{\mathrm{0}}{u}_{\mathrm{0}})=\left\{\begin{array}{cc}f(u_{\mathrm{0}}{u}_i)+\mathrm{4},& i\ge \mathrm{7}\mathrm{a}\mathrm{n}\mathrm{d}i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ f(u_{\mathrm{0}}{u}_i)+\mathrm{3},& i\ge \mathrm{7}\mathrm{a}\mathrm{n}\mathrm{d}i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

f(v_{\mathrm{0}}{w}_{\mathrm{0}})=\left\{\begin{array}{cc}f(v_{\mathrm{0}}{v}_j)+\mathrm{3},& j\ge \mathrm{7}\mathrm{a}\mathrm{n}\mathrm{d}j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ f(v_{\mathrm{0}}{v}_j)+\mathrm{1},& j\ge \mathrm{7}\mathrm{a}\mathrm{n}\mathrm{d}j\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

f(u_{\mathrm{0}}{w}_{\mathrm{0}})=\left\{\begin{array}{cc}f(w_{\mathrm{0}}{w}_m)+\mathrm{2},& m\ge \mathrm{7}\mathrm{a}\mathrm{n}\mathrm{d}m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ f(w_{\mathrm{0}}{w}_m)+\mathrm{5},& m\ge \mathrm{7}\mathrm{a}\mathrm{n}\mathrm{d}m\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

当m=i=j\ge \mathrm{7}时，若m=i=j=n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})，则

f(u_{\mathrm{0}}{u}_i)=\mathrm{3}i-\mathrm{1}=\mathrm{3}n-\mathrm{1}

f(v_{\mathrm{0}}{v}_j)=\mathrm{3}j=\mathrm{3}n

f(w_{\mathrm{0}}{w}_m)=\mathrm{3}m-\mathrm{2}=\mathrm{3}n-\mathrm{2}

此时，

f(v_{\mathrm{0}}{w}_{\mathrm{0}})=f(v_{\mathrm{0}}{v}_j)+\mathrm{1}=\mathrm{3}n+\mathrm{1}

f(v_{\mathrm{0}}{u}_{\mathrm{0}})=f(u_{\mathrm{0}}{u}_i)+\mathrm{3}=\mathrm{3}n-\mathrm{1}+\mathrm{3}=\mathrm{3}n+\mathrm{2}f(u_{\mathrm{0}}{w}_{\mathrm{0}})=f(w_{\mathrm{0}}{w}_m)+\mathrm{5}=\mathrm{3}n-\mathrm{2}+\mathrm{5}=\mathrm{3}n+\mathrm{3}

可知，边标号序列为\mathrm{1}\to \mathrm{3}n+\mathrm{3}。对于标号和

\begin{array}{l}\mathrm{S}\mathrm{u}\mathrm{m}(d(v_{\mathrm{0}}))=\mathrm{1}+\mathrm{5}+\mathrm{7}+\mathrm{12}+\mathrm{15}+\\ \mathrm{18}+\mathrm{19}+\mathrm{24}+\dots +\\ \mathrm{3}j-\mathrm{2}+\mathrm{3}j+\mathrm{3}n+\mathrm{2}+\mathrm{3}n+\mathrm{1}=\\ \mathrm{102}+\mathrm{12}n\end{array}

\begin{array}{l}\mathrm{S}\mathrm{u}\mathrm{m}(d(u_{\mathrm{0}}))=\mathrm{3}+\mathrm{4}+\mathrm{8}+\mathrm{11}+\mathrm{13}+\\ \mathrm{17}+\mathrm{20}+\mathrm{23}+\dots +\mathrm{3}i-\mathrm{1}+\\ \mathrm{3}i-\mathrm{1}+\mathrm{3}n+\mathrm{2}+\mathrm{3}n+\mathrm{3}=\\ \mathrm{102}+\mathrm{12}n\end{array}

\begin{array}{l}\mathrm{S}\mathrm{u}\mathrm{m}(d(w_{\mathrm{0}}))=\mathrm{2}+\mathrm{6}+\mathrm{9}+\mathrm{10}+\mathrm{14}+\\ \mathrm{16}+\mathrm{21}+\mathrm{22}+\dots +\mathrm{3}m+\\ \mathrm{3}m-\mathrm{2}+\mathrm{3}n+\mathrm{3}+\mathrm{3}n+\mathrm{1}=\\ \mathrm{102}+\mathrm{12}n\end{array}

可得

\mathrm{S}\mathrm{u}\mathrm{m}(d(v_{\mathrm{0}}))=\mathrm{S}\mathrm{u}\mathrm{m}(d(u_{\mathrm{0}}))=\mathrm{S}\mathrm{u}\mathrm{m}(d(w_{\mathrm{0}}))

因此，当m=i=j\ge \mathrm{7}时，若m=i=j=n\equiv\mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})，C_{\mathrm{3}}^H是AVSREL图，其中H=\{S_i,S_j,S_m\}。

同理，当m=i=j\ge \mathrm{7}时，若m=i=j=n\equiv\mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),C_{\mathrm{3}}^H是AVSREL图，其中H=\{S_i,S_j,S_m\}。

4　 结 语

本文在已有的图的可约染色和图的顶点魔幻边标号概念基础上，提出了新的邻点和可约边标号概念，并通过设计相关算法，得出了部分定理并给出了证明。

参考文献

[1] ROSA A. On certain valuations of the vertices of a graph ［EB/OL］. ［2020-12-12］.

[2] 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 .

[3] MACDOUGALL J A， MILLER M， WALLIS W D. Vertex-magic total labelings of graphs ［J］. Utilitas Mathematics， 2002，61：3-21. DOI：10.1088/1742-6596/1724/1/012040 .

[4] BURRIS A C， SCHELP R H. Vertex-distinguishing proper edge-colorings ［J］. Journal of Graph Theory， 1997， 26（2）：73-82. DOI：10.1002/（sici）1097-0118（199710）26： 273： aid-jgt2>3.0.co；2-c .

[5] LI J W， ZHANG Z F， ZHU E Q， et al. Adjacent vertex reducible edge-total coloring of graphs ［C］//2009 2nd International Conference on Biomedical Engineering and Informatics. New York： IEEE Press， 2009： 1-3. DOI：10.1109/BMEI.2009.5304740 .

[6] FLANDRIN E， MARCZYK A， PRZYBYŁO J， et al. Neighbor sum distinguishing index ［J］. Graphs and Combinatorics， 2013， 29（5）： 1329-1336. DOI：10.1007/s00373-012-1191-x .

[7] PILŚNIAK M， WOŹNIAK M. On the total-neighbor-distinguishing index by sums ［J］. Graphs and Combinatorics， 2015， 31（3）： 771-782. DOI：10.1007/s00373-013-1399-4 .

[8] 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 .

基金资助

国家自然科学基金(11961041)

国家自然科学基金(62062049)

国家自然科学基金(11461038)