若干类联图的邻点可约边标号

Adjacent vertex reducible edge labeling of the several compound graphs

摘要

对于一个简单无向连通图G\left(V,E\right)，若存在映射f:E\left(G\right)\to \left\{\mathrm{1,2},\cdots ,|E|\right\}，且对于图中所有相邻且度相同的顶点，都有标号和相同，则称f为图G的邻点可约边标号（AVREL）.本文在学习研究已有图标号算法的基础上，设计了一种启发式搜索算法，利用该算法对15个顶点以内的联图进行标号，得到了邻点可约边标号的结果集.接着分析结果集，总结圈图与路图、星图和完全图形成的各类联图在有限点内的标号规律，并给出相关定理及证明.

Abstract

For a simple undirected connected graph G\left(V,E\right)， f is said to be the adjacent vertex reducible edge labeling （AVREL） of the graph G if there exists a mapping f:E\left(G\right)\to \left\{\mathrm{1,2},\dots ,|E|\right\} that is labeled and identical for all adjacent vertices in the graph with the same degree. On the basis of learning and studying the existing graph labeling algorithms， a heuristic search algorithm is designed， using which to label the union graphs with 15 vertices or less， and obtain the result set of adjacent vertex reducible edge labeling. The result set is analyzed to summarize the labeling laws within finite points for various types of union graphs formed by circle graphs and path graphs， star graphs and complete graphs， and the related theorems and proofs are given.

Graphical abstract

关键词

圈图 / 联图 / 邻点可约边标号 / 标号算法

Key words

circle graphs / compound graphs / adjacent vertex reducible edge labeling / labeling algorithm

图论^［1］的发源可追溯至一个经典而具有挑战性的问题，即柯尼斯堡七桥问题.1738年，瑞士数学家欧拉通过解决这一问题，为图论的诞生奠定了基础.因此，欧拉被认为是图论的创始人.图标号作为图论的一个分支，其起源可以追溯到Rosa^［2］在1967年的论文中提出的标号问题.2002年，MacDougall等^［3］提出了顶点魔幻全标号的概念，该标号被越来越多的学者关注和研究.2004年，张忠辅等^［4］提出了邻点可区别全染色的概念.2007年，文献［5］在优美标号、超幻和标号以及调和标号等问题上取得了新的研究进展，并成功证明了相关的猜想.2009年，张忠辅等^［6］在可区别染色的理论基础上，提出了可约染色的概念，现在已有许多学者对其进行研究，并得到一系列成果^［7-8］.2012年，刘家保等^［9-10］探索并研究了双圈图的奇优美标号.2023年，文献［11-12］在图染色概念基础上，提出了邻点和可约边染色的新概念.

在运输网络中，边的权值表示节点之间的流通量，节点的权值表示总的容纳量，即其关联边的权值之和.针对联图中两个相邻同度点，要求其运输能力相同，将运输网络问题建模为一个图论问题，当道路多样性达到极值时，可以用邻点可约边标号模型进行描述.本文设计并实现了邻点可约边标号（adjacent vertex reducible edge labeling， AVREL）算法，该算法通过递归搜索解空间，筛选出满足AVREL条件的图集，并将标号结果以矩阵的形式输出，对有限点内的若干类联图图集进行实验，得到了实验结果集，接着分析结果集得出相关定理并给出证明.

1 预备知识

定义1 设G\left(V,E\right)是一个简单图，若存在一一映射f:E\left(G\right)\to \left\{\mathrm{1,2},\dots ,|E|\right\}，使得对任意两点uv\in E(G)，如果d\left(u\right)=d\left(v\right)，有S\left(u\right)=S(v)，其中，S\left(u\right)={\sum }_{uw\in E(G)}f(uw)，d\left(u\right)表示点u的度，则称f为G的邻点可约边标号（AVREL），图G为AVREL图；若图不存在AVREL，则称该图为非AVREL图.

定义2 设G是简单图，联图G{\downarrow }_{m}G\left(m\ge \mathrm{2}\right)是指将m个图G共边形成的图，如图1 a所示.

定义3 设简单连通图G和H属于路P_n、圈C_n、星S_n、扇F_n、轮W_n、完全图K_n，约定用符号a表示星、扇、轮图的中心节点，路图的1度点，圈图的任意一点，完全图的任意一点.符号b表示星、轮图的非中心节点，扇图的2度点，路图的2度点.符号c表示扇图的3度非中心节点.联图G{\uparrow }_{aa}H是指将G的a节点连接到H的a节点，如图1 b所示.

定义4 设串图（Bunch）B_{C_n}^m为m\left(m\ge \mathrm{2}\right)个阶数为n\left(n\ge \mathrm{4},n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\right)的圈图相连的图，如图1c所示，是B_{C_{\mathrm{4}}}^{\mathrm{2}}示例图.

定义5 设G和H是两个简单图，其顶点数分别为n_{\mathrm{1}}、n_{\mathrm{2}}，边数分别为m_{\mathrm{1}}、m_{\mathrm{2}}.G和H的冠图定义为：由图G的每一个顶点都连接一个图H，连接点为H的所有顶点，简记为G\circ H.易得，冠图G\circ H的顶点数为n_{\mathrm{1}}(\mathrm{1}+n_{\mathrm{2}})，边数为m_{\mathrm{1}}+n_{\mathrm{1}}{n}_{\mathrm{2}}+n_{\mathrm{1}}{m}_{\mathrm{2}}.例如，G=C_{\mathrm{4}}，H=P_{\mathrm{2}}，图G和图H的冠图C_{\mathrm{4}}\circ P_{\mathrm{2}}，如图2 a所示.

定义6 设G和H是两个简单图，由图G的每一个x节点都连接一个图H，连接点为H的y节点，称为广义冠图，简记为G^x\circ H^y，其中，x,y表示不同阶数的点.例如，G的x节点有3类，用a,b,c表示（a表示星、扇、轮、友谊图和完全图的中心节点，路图的1度点，圈图的任意一点，联图的最大度点；b表示星、轮、友谊图和完全图的非中心节点，扇图的2度点，路图的2度点，联图的次最大度点；c表示扇图的3度非中心节点，联图的最小度点），H的y节点有2类，用a,b表示.G=W_{\mathrm{8}}，H=S_{\mathrm{3}}，图G和图H的广义冠图W_{\mathrm{8}}^b\circ S_{\mathrm{3}}^a，如图2 b所示.

2 AVREL算法

2.1 算法思想

AVREL算法思想是输入图G的邻接矩阵、初始化矩阵，根据约束条件构造解空间\phi \left(V,E\right)，对图集的解空间进行递归搜索，筛选出满足AVREL的图集，并将标号结果以矩阵的形式输出，算法结束；若搜索完解空间仍没有满足AVREL的解，输出图G为非AVREL图，算法结束.

1） 预处理函数Pre-processing：计算图G的顶点数V、边数E、度序列Degree及相邻同度点集合SameDegree等属性，确定解空间\phi \left(V,E\right).

2） 分类函数Classify：利用分类函数将相邻同度点划分在一个集合，其他顶点划分在另一个集合里.

3） 平衡函数IsBalance：判断搜索解空间时是否出现了满足AVREL的图，若满足，记录其标号矩阵，记为标号矩阵LabelMatrix.

4） 递归搜索：递归搜索解空间，利用平衡函数判断搜索解空间时是否出现满足AVREL标号的矩阵，选择出满足条件的图集，输出最终的标号矩阵，算法结束；若搜索完图集的解空间没有满足AVREL约束条件的解，则该图为非AVREL图，算法结束.

2.2 算法伪代码

算法伪代码如下所示：

2.3 实验结果分析

利用AVREL算法，对4~15个顶点以内的圈图进行实验，得到这些顶点的邻点可约边标号结果集，如表1所示.

2.4 AVREL标号示例

AVREL标号示例如图3所示.

3 定理及证明

定理1 对于广义冠图C_n^a\circ S_m^a\left(n\ge \mathrm{3},m\ge \mathrm{2}\right)，除了n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right),m\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)以外的图，均为AVREL图（见图4）.

证明 设广义冠图C_n^a\circ S_m^a的顶点集为V\left(C_n^a\circ S_m^a\right)=\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n\right\}\bigcup \left\{v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{mn}\right\}，边集为E\left(C_n^a\circ S_m^a\right)=\{u_i{u}_{i+\mathrm{1}}|\mathrm{1}\le i\le n-\mathrm{1}\bigcup \left\{u_n{u}_{\mathrm{1}}\right\}\bigcup

\left\{u_i{v}_i,u_i{v}_{\left(m-\mathrm{2}\right)n+i},u_i{v}_{\left(m-\mathrm{1}\right)n+i}|\mathrm{1}\le i\le n\right\}.

情形1 当n,m\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，广义冠图C_n^a\circ S_m^a的邻点可约边标号为：

设n=\mathrm{2}k+\mathrm{1},m=\mathrm{2}l+\mathrm{1},k,l=\mathrm{1,2},\cdots .

\begin{array}{l}f\left(u_n{u}_{\mathrm{1}}\right)=k+\mathrm{1},\\ f\left(u_i{v}_i\right)=\mathrm{4}k-i+\mathrm{3},\mathrm{1}\le i\le \mathrm{2}k+\mathrm{1},\end{array}

此时图4中只存在1度点和m+\mathrm{2}度点，其中的1度点是不相邻的，所以不需要考虑，只需要保证相邻的m+\mathrm{2}度点标号和相同.图中\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n\right\}均为相邻的m+\mathrm{2}度点，当\mathrm{1}\le i\le n时，

\begin{array}{l}Sum\left(u_i\right)={\sum }_{uu\in E\left(u_i\right)}f\left(uu\right)=\\ \left\{f\left(u_{i-\mathrm{1}}{u}_i\right)+f\left(u_i{u}_{i+\mathrm{1}}\right)+f\left(u_i{v}_i\right)+\cdots +f\left(u_i{v}_{\left(m-\mathrm{2}\right)n+i}\right)+f\left(u_i{v}_{\left(m-\mathrm{1}\right)n+i}\right)\right\}\Vert \\ \left\{f\left(u_n{u}_{\mathrm{1}}\right)+f\left(u_{\mathrm{1}}{u}_{\mathrm{2}}\right)+f\left(u_{\mathrm{1}}{v}_{\mathrm{1}}\right)+\cdots +f\left(u_{\mathrm{1}}{v}_{\left(m-\mathrm{2}\right)n+\mathrm{1}}\right)+f\left(u_{\mathrm{1}}{v}_{\left(m-\mathrm{1}\right)n+\mathrm{1}}\right)\right\}\Vert \\ \left\{f\left(u_{n-\mathrm{1}}{u}_n\right)+f\left(u_n{u}_{\mathrm{1}}\right)+f\left(u_n{v}_n\right)+\cdots +f\left(u_n{v}_{\left(m-\mathrm{1}\right)n}\right)+f\left(u_n{v}_{mn}\right)\right\}=\\ \left\{\frac{i}{\mathrm{2}}+\left(k+\frac{i}{\mathrm{2}}+\mathrm{1}\right)+\left(\mathrm{4}k-i+\mathrm{3}\right)+\cdots +\left(\mathrm{2}l+\mathrm{2}\right)\left(\mathrm{2}k+\mathrm{1}\right)+\mathrm{2}l\left(\mathrm{2}k+\mathrm{1}\right)+\mathrm{1}\right\}\Vert \\ \left\{\left(k+\mathrm{1}\right)+\mathrm{1}+\left(\mathrm{4}k+\mathrm{2}\right)+\cdots +\left(\mathrm{2}l+\mathrm{2}\right)\left(\mathrm{2}k+\mathrm{1}\right)+\mathrm{2}l\left(\mathrm{2}k+\mathrm{1}\right)+\mathrm{1}\right\}\Vert \\ \left\{\left(\mathrm{2}k+\mathrm{1}\right)+\left(k+\mathrm{1}\right)+\left(\mathrm{2}k+\mathrm{2}\right)+\cdots +\left(\mathrm{2}l+\mathrm{2}\right)\left(\mathrm{2}k+\mathrm{1}\right)+\mathrm{2}l\left(\mathrm{2}k+\mathrm{1}\right)+\mathrm{1}\right\}=\\ \left\{\mathrm{5}k+\mathrm{4}+l^{\mathrm{2}}\left(\mathrm{4}k+\mathrm{2}\right)+l\left(\mathrm{8}k+\mathrm{5}\right)\right\}.\end{array}

其中，出现的符号“||”表示为逻辑或.

由上述证明过程可以确定广义冠图C_n^a\circ S_m^a\left(n\ge \mathrm{3},m\ge \mathrm{2}\right)当n,m\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，相邻同度点的边标号和为常数.根据AVREL定义，情形1是AVREL图，得证.

情形2 当m\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，广义冠图C_n^a\circ S_m^a的邻点可约边标号为：

设m=\mathrm{2}k,k=\mathrm{1,2},\cdots .

\begin{array}{c}f\left(u_i{u}_{i+\mathrm{1}}\right)=i,\mathrm{1}\le i\le n-\mathrm{1},\\ f\left(u_n{u}_{\mathrm{1}}\right)=n,\\ f\left(u_{\mathrm{1}}{v}_{\mathrm{1}}\right)=n+\mathrm{1},\\ f\left(u_i{v}_i\right)=\mathrm{2}n-i+\mathrm{2},\mathrm{2}\le i\le n,\\ f\left(u_i{v}_{n+i}\right)=\mathrm{3}n-i+\mathrm{1},\mathrm{1}\le i\le n,\\ f\left(u_i{v}_{\left(m-\mathrm{2}\right)n+i}\right)=\left(\mathrm{2}k+\mathrm{1}\right)n-i+\mathrm{1},\\ \mathrm{1}\le i\le n,k=\mathrm{2,3},\cdots ,m/\mathrm{2},\\ f\left(u_i{v}_{\left(m-\mathrm{1}\right)n+i}\right)=\left(\mathrm{2}k-\mathrm{1}\right)n+i,\\ \mathrm{1}\le i\le n,k=\mathrm{2,3},\cdots ,m/\mathrm{2}.\end{array}

图4中有1度点和m+\mathrm{2}度点，由于所有的1度点是不相邻的，所以不用考虑，只需考虑所有相邻的m+\mathrm{2}度点标号和相同即可.\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n\right\}均为相邻的m+\mathrm{2}度点，当\mathrm{1}\le i\le n时，

\begin{array}{l}Sum\left(u_i\right)={\sum }_{uu\in E\left(u_i\right)}f\left(uu\right)=\\ \left\{f\left(u_{i-\mathrm{1}}{u}_i\right)+f\left(u_i{u}_{i+\mathrm{1}}\right)+f\left(u_i{v}_i\right)+f\left(u_i{v}_{n+i}\right)+\cdots +f\left(u_i{v}_{\left(m-\mathrm{2}\right)n+i}\right)+f\left(u_i{v}_{\left(m-\mathrm{1}\right)n+i}\right)\right\}\Vert \\ \left\{f\left(u_n{u}_{\mathrm{1}}\right)+f\left(u_{\mathrm{1}}{u}_{\mathrm{2}}\right)+f\left(u_{\mathrm{1}}{v}_{\mathrm{1}}\right)+f\left(u_{\mathrm{1}}{v}_{n+\mathrm{1}}\right)+\cdots +f\left(u_{\mathrm{1}}{v}_{\left(m-\mathrm{2}\right)n+\mathrm{1}}\right)+f\left(u_{\mathrm{1}}{v}_{\left(m-\mathrm{1}\right)n+\mathrm{1}}\right)\right\}\Vert \\ \left\{f\left(u_{n-\mathrm{1}}{u}_n\right)+f\left(u_n{u}_{\mathrm{1}}\right)+f\left(u_n{v}_n\right)+f\left(u_n{v}_{\mathrm{2}n}\right)+\cdots +f\left(u_n{v}_{\left(m-\mathrm{1}\right)n}\right)+f\left(u_n{v}_{mn}\right)\right\}=\\ \left\{\left(i-\mathrm{1}\right)+i+\left(\mathrm{2}n-i+\mathrm{2}\right)+\left(\mathrm{3}n-i+\mathrm{1}\right)+\cdots +\mathrm{4}kn+\mathrm{1}\right\}\Vert \\ \left\{n+\mathrm{1}+\left(n+\mathrm{1}\right)+\mathrm{3}n+\cdots +\mathrm{4}kn+\mathrm{1}\right\}\Vert \end{array}

\begin{array}{l}\left\{\left(n-\mathrm{1}\right)+n+\left(n+\mathrm{2}\right)+\left(\mathrm{2}n+\mathrm{1}\right)+\cdots +\mathrm{4}kn+\mathrm{1}\right\}=\\ \left\{\mathrm{5}n+\mathrm{2}+\mathrm{2}n{k}^{\mathrm{2}}+\mathrm{2}nk-\mathrm{4}n+k-\mathrm{1}\right\}=\left\{\mathrm{2}n{k}^{\mathrm{2}}+\mathrm{2}nk+n+k+\mathrm{1}\right\}.\end{array}

由上述证明过程可以确定广义冠图C_n^a\circ S_m^a\left(n\ge \mathrm{3},m\ge \mathrm{2}\right)当m\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，相邻同度点的边标号和为常数.根据VREL定义，情形2是AVREL图，得证.

综上，由情形1和情形2可以确定f\left(E\left(C_n^a\circ S_m^a\right)\right)\to \left\{\mathrm{1,2},\cdots ,n+nm\right\}的一一映射函数，且相邻同度点的边标号和为常数.根据AVREL定义，定理1证毕.

定理2 广义冠图C_n^a\circ S_{m+\mathrm{1}}^b(n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),m>\mathrm{1})是AVREL图（见图5）.

证明 设广义冠图C_n^a\circ S_{m+\mathrm{1}}^b的顶点集为V\left(C_n^a\circ S_{m+\mathrm{1}}^b\right)=\left\{u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n\right\}\bigcup \left\{v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{\left(m+\mathrm{1}\right)n}\right\}，边集为E\left(C_n^a\circ S_{m+\mathrm{1}}^b\right)=\left\{v_i{v}_{n+\left(i-\mathrm{1}\right)m+l+\mathrm{2}}\right.|\mathrm{1}\le i\le n,\left.-\mathrm{1}\le l\le m-\mathrm{1}\right\}\bigcup \left\{u_i{u}_{i+\mathrm{1}}|\mathrm{1}\le i\le n-\mathrm{1}\right\}\bigcup \left\{u_i{v}_i\right.|\mathrm{1}\lei\left.\le n\right\}\bigcup \left\{u_n{u}_{\mathrm{1}}\right\}.

当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right),m>\mathrm{1}时，广义冠图C_n^a\circ S_{m+\mathrm{1}}^b的邻点可约边标号为：

设n=\mathrm{2}k+\mathrm{1},k=\mathrm{1,2},\cdots .

\begin{array}{c}f\left(u_i{u}_{i+\mathrm{1}}\right)=\left\{\begin{array}{l}\mathrm{3}k-\frac{i}{\mathrm{2}}+\mathrm{2},i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right),\\ \mathrm{4}k-\frac{i+\mathrm{1}}{\mathrm{2}}+\mathrm{3},i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right).\end{array}\right.\\ f\left(u_i{v}_i\right)=i,\mathrm{1}\le i\le \mathrm{2}k+\mathrm{1},\\ f\left(u_n{u}_{\mathrm{1}}\right)=\mathrm{3}k+\mathrm{2},\\ f\left(v_i{v}_{n+\left(i-\mathrm{1}\right)m+l+\mathrm{2}}\right)=\left(i-\mathrm{1}\right)m+\mathrm{4}k+l+\mathrm{4},\\ \mathrm{1}\le i\le m,l=-\mathrm{1,0},\cdots ,m-\mathrm{2}.\end{array}

图5中存在1度点、3度点和m+\mathrm{1}度点，其中，1度点和m+\mathrm{1}度点是分别不相邻的，所以不需要考虑，只需要保证每个圈图上相邻的3度点标号和分别相同即可.图中\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n\right\}分别为相邻的3度点，当\mathrm{1}\le i\le n时，

\begin{array}{l}Sum\left(u_i\right)={\sum }_{uu\in E\left(u_i\right)}f\left(uu\right)=\\ \left\{f\left(u_{i-\mathrm{1}}{u}_i\right)+f\left(u_i{u}_{i+\mathrm{1}}\right)+f\left(u_i{v}_i\right)\right\}\Vert \left\{f\left(u_{\mathrm{1}}{u}_{\mathrm{2}}\right)+f\left(u_n{u}_{\mathrm{1}}\right)+f\left(u_{\mathrm{1}}{v}_{\mathrm{1}}\right)\right\}\Vert \\ \left\{f\left(u_n{u}_{\mathrm{1}}\right)+f\left(u_{n-\mathrm{1}}{u}_n\right)+f\left(u_n{v}_n\right)\right\}=\\ \left\{\left(\mathrm{3}k-\frac{i}{\mathrm{2}}+\mathrm{2}\right)+\left(\mathrm{4}k-\frac{i}{\mathrm{2}}+\mathrm{3}\right)+i\right\}\Vert \left\{\left(\mathrm{4}k-\mathrm{1}+\mathrm{3}\right)+\left(\mathrm{3}k+\mathrm{2}\right)+\mathrm{1}\right\}\Vert \\ \left\{\left(\mathrm{3}k+\mathrm{2}\right)+\left(\mathrm{2}k+\mathrm{2}\right)+\left(\mathrm{2}k+\mathrm{1}\right)\right\}=\left\{\mathrm{7}k+\mathrm{5}\right\}.\end{array}

由上述证明过程可以确定f\left(E\left(C_n^a\circ S_{m+\mathrm{1}}^b\right)\right)\to \left\{\mathrm{1,2},\cdots ,\left(\mathrm{2}+m\right)n\right\}的一一映射的函数，且相邻同度点的边标号和为常数.根据AVREL定义，定理2证毕.

定理3 广义冠图C_n^a\circ {\left(K_{\mathrm{4}}{\uparrow }_{aa}{P}_{\mathrm{2}}\right)}^b\left(n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\right)是AVREL图（见图6）.

证明 设广义冠图C_n^a\circ {\left(K_{\mathrm{4}}{\uparrow }_{aa}{P}_{\mathrm{2}}\right)}^b的顶点集为V\left(C_n^a\circ {\left(K_{\mathrm{4}}{\uparrow }_{aa}{P}_{\mathrm{2}}\right)}^b\right)=\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n\right\}\bigcup\{v_{\mathrm{11}},v_{\mathrm{12}},\cdots ,v_{n\mathrm{4}}｝，边集为E\left(C_n^a\circ {\left(K_{\mathrm{4}}{\uparrow }_{aa}{P}_{\mathrm{2}}\right)}^b\right)=\left\{u_n{u}_{\mathrm{1}}\right\}\bigcup\left\{u_i{v}_{ij},v_{ij}{v}_{i\left(j+\mathrm{1}\right)}|\mathrm{1}\le i\le n,\mathrm{1}\le j\le \mathrm{3}\right\}\bigcup\left\{v_{ij}{v}_{i\left(j+\mathrm{2}\right)}|\mathrm{1}\le i\le n,j=\mathrm{1}\right\}\bigcup \left\{u_i{u}_{i+\mathrm{1}}|\mathrm{1}\le i\le n-\mathrm{1}\right\}.

当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，广义冠图C_n^a\circ {\left(K_{\mathrm{4}}{\uparrow }_{aa}{P}_{\mathrm{2}}\right)}^b的邻点可约边标号为：

设n=\mathrm{2}k+\mathrm{1},k=\mathrm{1,2},\cdots .

\begin{array}{c}f\left(u_n{u}_{\mathrm{1}}\right)=\mathrm{15}k+\mathrm{8}.\\ f\left(u_i{v}_{ij}\right)=\left\{\begin{array}{l}\mathrm{4}k+i+\mathrm{2},\mathrm{1}\le i\le \mathrm{2}k+\mathrm{1},j=\mathrm{1},\\ i,\mathrm{1}\le i\le \mathrm{2}k+\mathrm{1},j=\mathrm{2},\\ \mathrm{4}k-i+\mathrm{3},\mathrm{1}\le i\le \mathrm{2}k+\mathrm{1},j=\mathrm{3}.\end{array}\right.\\ f\left(v_{ij}{v}_{i\left(j+\mathrm{1}\right)}\right)=\left\{\begin{array}{l}\mathrm{8}k+i+\mathrm{4},\mathrm{1}\le i\le \mathrm{2}k+\mathrm{1},j=\mathrm{1},\\ \mathrm{12}k-i+\mathrm{7},\mathrm{1}\le i\le \mathrm{2}k+\mathrm{1},j=\mathrm{2},\\ \mathrm{12}k+i+\mathrm{6},\mathrm{1}\le i\le \mathrm{2}k+\mathrm{1},j=\mathrm{3}.\end{array}\right.\\ f\left(v_{ij}{v}_{i\left(j+\mathrm{2}\right)}\right)=\mathrm{8}k-i+\mathrm{5},\mathrm{1}\le i\le \mathrm{2}k+\mathrm{1},j=\mathrm{1}.\end{array}

图6中存在1度点、3度点、4度点和5度点，其中，相邻同度点有3度点和5度点，所以1度点和4度点不需要考虑，只需要保证每个轮图上相邻的3度点与每个圈图上相邻的5度点标号和分别相同即可.图中\left\{v_{\mathrm{11}},v_{\mathrm{12}},\cdots ,v_{n\mathrm{1}},v_{n\mathrm{2}}\right\}与\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n\right\}分别为相邻的3度点与5度点，标号和分别为：

\begin{array}{l}{S}_{\mathrm{3}}=\left\{{\sum }_{uu\in E\left(u_i\right)}f\left(uu\right)\right\}=\left\{f\left(u_i{v}_{i\mathrm{1}}\right)+f\left(v_{i\mathrm{1}}{v}_{i\mathrm{2}}\right)+f\left(v_{i\mathrm{1}}{v}_{i\mathrm{3}}\right)\right\}||\left\{f\left(u_i{v}_{i\mathrm{2}}\right)+f\left(v_{i\mathrm{1}}{v}_{i\mathrm{2}}\right)+f\left(v_{i\mathrm{2}}{v}_{i\mathrm{3}}\right)\right\}=\\ \left\{\left(\mathrm{4}k+\mathrm{3}\right)+\left(\mathrm{8}k+\mathrm{5}\right)+\left(\mathrm{8}k+\mathrm{4}\right)\right\}||\left\{\mathrm{1}+\left(\mathrm{8}k+\mathrm{5}\right)+\left(\mathrm{12}k+\mathrm{6}\right)\right\}=\left\{\mathrm{20}k+\mathrm{12}\right\};\\ S_{\mathrm{5}}=\left\{{\sum }_{uu\in E\left(u_i\right)}f\left(uu\right)\right\}=\left\{f\left(u_n{u}_{\mathrm{1}}\right)+f\left(u_{\mathrm{1}}{u}_{\mathrm{2}}\right)+f\left(u_{\mathrm{1}}{v}_{\mathrm{11}}\right)+f\left(u_{\mathrm{1}}{v}_{\mathrm{12}}\right)+f\left(u_{\mathrm{1}}{v}_{\mathrm{13}}\right)\right\}||\cdots ||\\ \left\{f\left(u_{n-\mathrm{1}}{u}_n\right)+f\left(u_n{u}_{\mathrm{1}}\right)+f\left(u_n{v}_{n\mathrm{1}}\right)+f\left(u_n{v}_{n\mathrm{2}}\right)+f\left(u_n{v}_{n\mathrm{3}}\right)\right\}=\\ \left\{\left(\mathrm{15}k+\mathrm{8}\right)+\left(\mathrm{16}k+\mathrm{8}\right)+\left(\mathrm{4}k+\mathrm{3}\right)+\mathrm{1}+\left(\mathrm{4}k+\mathrm{2}\right)\right\}||\cdots ||\\ \left\{\left[\mathrm{15}k-\left(n-\mathrm{1}\right)/\mathrm{2}+\mathrm{8}\right]+\left(\mathrm{15}k+\mathrm{8}\right)+\left(\mathrm{4}k+n+\mathrm{2}\right)+n+\left(\mathrm{4}k-n+\mathrm{3}\right)\right\}=\left\{\mathrm{39}k+\mathrm{22}\right\}.\end{array}

由上述证明过程可以确定f\left(E\left(C_n^a\circ {\left(K_{\mathrm{4}}{\uparrow }_{aa}{P}_{\mathrm{2}}\right)}^b\right)\right)\to \left\{\mathrm{1,2},\cdots ,\mathrm{8}n\right\}的一一映射的函数，且相邻同度点的边标号和为常数.根据AVREL定义，定理3证毕.

定理4 联图C_{\mathrm{3}}{\downarrow }_m{C}_{\mathrm{3}}\left(m\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\right)是AVREL图（见图7）.

证明 设联图C_{\mathrm{3}}{\downarrow }_m{C}_{\mathrm{3}}的顶点集为V\left(C_{\mathrm{3}}{\downarrow }_m{C}_{\mathrm{3}}\right)=\left\{u_{\mathrm{1}},u_{\mathrm{2}}\right\}\bigcup \left\{v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_m\right\}，边集E\left(C_{\mathrm{3}}{\downarrow }_m{C}_{\mathrm{3}}\right)=\left\{u_{\mathrm{1}}{u}_{\mathrm{2}}\right\}\bigcup \left\{v_i{u}_j|\mathrm{1}\le i\le m,\mathrm{1}\le j\le \mathrm{2}\right\}.

当m\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，联图C_{\mathrm{3}}{\downarrow }_m{C}_{\mathrm{3}}的邻点可约边标号为：

设m=\mathrm{2}k,k=\mathrm{1,2},\cdots .

\begin{array}{l}f\left(v_i{u}_j\right)=\mathrm{2}\left(i-\mathrm{1}\right)+j,\\ i=\mathrm{1},\mathrm{3},\cdots ,\mathrm{2}k-\mathrm{1},j=\mathrm{1},\mathrm{2},\end{array}

\begin{array}{c}f\left(v_i{u}_j\right)=\left\{\begin{array}{l}\mathrm{2}\left(i-\mathrm{1}\right)+\mathrm{2},j=\mathrm{1},\\ \mathrm{2}\left(i-\mathrm{1}\right)+\mathrm{1},j=\mathrm{2},\end{array}\right.\\ i=\mathrm{2},\mathrm{4},\cdots ,\mathrm{2}k.\\ f\left(u_{\mathrm{1}}{u}_{\mathrm{2}}\right)=\mathrm{4}k+\mathrm{1}.\end{array}

图7中存在2度点和m+\mathrm{1}度点，其中，2度点是不相邻的，所以不需要考虑，只需要保证相邻的m+\mathrm{1}度点标号和相同即可.图中\left\{u_{\mathrm{1}},u_{\mathrm{2}}\right\}为相邻的m+\mathrm{1}度点，当\mathrm{1}\le i\le \mathrm{2}时，

\begin{array}{l}Sum\left(u_i\right)=\left\{{\sum }_{uu\in E\left(u_i\right)}f\left(uu\right)\right\}=\\ \left\{f\left(u_{\mathrm{1}}{u}_{\mathrm{2}}\right)+f\left(v_i{u}_{\mathrm{1}}\right)\right\}\Vert \left\{f\left(u_{\mathrm{1}}{u}_{\mathrm{2}}\right)+f\left(v_i{u}_{\mathrm{2}}\right)\right\}=\\ \left\{\left(\mathrm{4}k+\mathrm{1}\right)+{\displaystyle \sum _{i=\mathrm{1,3}}^{\mathrm{2}k-\mathrm{1}}}\left[\mathrm{2}\left(i-\mathrm{1}\right)+\mathrm{1}\right]+{\displaystyle \sum _{i=\mathrm{2,4}}^{\mathrm{2}k}}\left[\mathrm{2}\left(i-\mathrm{1}\right)+\mathrm{2}\right]\right\}\Vert \\ \left\{\left(\mathrm{4}k+\mathrm{1}\right)+{\displaystyle \sum _{i=\mathrm{1,3}}^{\mathrm{2}k-\mathrm{1}}}\left[\mathrm{2}\left(i-\mathrm{1}\right)+\mathrm{2}\right]+{\displaystyle \sum _{i=\mathrm{2,4}}^{\mathrm{2}k}}\left[\mathrm{2}\left(i-\mathrm{1}\right)+\mathrm{1}\right]\right\}=\\ \left\{\left(\mathrm{4}k+\mathrm{1}\right)+k+\mathrm{2}k+{\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{2}k}}\left[\mathrm{2}\left(i-\mathrm{1}\right)\right]\right\}\Vert \left\{\left(\mathrm{4}k+\mathrm{1}\right)+\mathrm{2}k+k+{\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{2}k}}\left[\mathrm{2}\left(i-\mathrm{1}\right)\right]\right\}=\\ \left\{\mathrm{7}k+\mathrm{1}+{\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{2}k}}\left[\mathrm{2}\left(i-\mathrm{1}\right)\right]\right\}=\left\{\mathrm{4}{k}^{\mathrm{2}}+\mathrm{5}k+\mathrm{1}\right\}.\end{array}

由上述证明过程可以确定f\left(E\left(C_{\mathrm{3}}{\downarrow }_m{C}_{\mathrm{3}}\right)\right)\to \left\{\mathrm{1,2},\cdots ,\mathrm{2}m+\mathrm{1}\right\}的一一映射的函数，且相邻同度点的边标号和为常数.根据AVREL定义，定理4证毕.

定理5 串图B_{C_{\mathrm{4}}}^m\left(m\ge \mathrm{2}\right)是AVREL图（见图8）.

证明 设串图B_{C_{\mathrm{4}}}^m的顶点集为V\left(B_{C_{\mathrm{4}}}^m\right)=\left\{u_{\mathrm{11}},u_{\mathrm{12}},\cdots ,u_{m\mathrm{4}}\right\}，边集为E\left(B_{C_{\mathrm{4}}}^m\right)=\left\{u_{i\mathrm{1}}{u}_{i\mathrm{4}},u_{ij}{u}_{i\left(j+\mathrm{2}\right)}\right.|\mathrm{1}\le i\le m,\left.j=\mathrm{1,2},\mathrm{3}\right\}.

当\mathrm{1}\le h\le m时，串图B_{C_{\mathrm{4}}}^m的邻点可约边标号为：

f\left(h{u}_{i}h{u}_{i+\mathrm{3}}\right)=\mathrm{4}m+\mathrm{1}-h,i=\mathrm{1},

\begin{array}{l}f\left(h{u}_{i}h{u}_{i+\mathrm{1}}\right)=\left\{\begin{array}{l}h,i=\mathrm{1},\\ \mathrm{2}m+h,i=\mathrm{2},\\ \mathrm{2}m-h+\mathrm{1},i=\mathrm{3}.\end{array}\right.\\ f\left[h{u}_i\left(h+\mathrm{1}\right)u_{i-\mathrm{2}}\right]=\mathrm{4}m+h,i=\mathrm{3},\\ f\left(h{u}_{i}m{u}_{i+\mathrm{2}}\right)=\mathrm{5}m,h=\mathrm{1},i=\mathrm{1}.\end{array}

图8中存在2度点和3度点，其中，相邻同度点有3度点，所以2度点不需要考虑，只需要保证相邻的3度点标号和相同即可.图中\left\{u_{\mathrm{11}},u_{\mathrm{12}},\cdots ,u_{m\mathrm{4}}\right\}为相邻的3度点，当\mathrm{1}\le i\le n-\mathrm{1}时，

\begin{array}{l}Sum\left(u_i\right)=\left\{{\sum }_{uu\in E\left(u_i\right)}f\left(uu\right)\right\}=\\ \left\{f\left(h{u}_{\mathrm{2}}h{u}_{\mathrm{3}}\right)+f\left(h{u}_{\mathrm{3}}h{u}_{\mathrm{4}}\right)+f\left[h{u}_{\mathrm{3}}\left(h+\mathrm{1}\right)u_{\mathrm{1}}\right]\right\}||\left\{f\left[h{u}_{\mathrm{3}}\left(h+\mathrm{1}\right)u_{\mathrm{1}}\right]+f\left(h{u}_{\mathrm{1}}h{u}_{\mathrm{2}}\right)+f\left(h{u}_{\mathrm{1}}h{u}_{\mathrm{4}}\right)\right\}=\\ \left\{\left(\mathrm{2}m+h\right)+\left(\mathrm{2}m-h+\mathrm{1}\right)+\left(\mathrm{4}m+h\right)\right\}||\left\{\left(\mathrm{4}m+h\right)+h+\left(\mathrm{4}m-h+\mathrm{1}\right)\right\}=\left\{\mathrm{8}m+h+\mathrm{1}\right\}.\end{array}

由上述证明过程可以确定f\left(E\left(B_{C_{\mathrm{4}}}^m\right)\right)\to \left\{\mathrm{1,2},\cdots ,\mathrm{5}m\right\}的一一映射的函数，且相邻同度点的边标号和为常数.根据AVREL定义，定理5证毕.

4 结语

本文在已有图标号的基础上，设计了一种邻点可约边标号算法，该算法针对AVREL解空间进行递归搜索，对4~15个顶点以内的若干类联图进行标号，得到标号结果集.通过分析结果集，当图G满足一定条件时，该图是AVREL图，推导出标号规律，总结定理并给出相关证明.

参考文献

[1] BONDY J A， MURTY U S R. Graph theory with applications ［M］. London： Macmillan， 1976.

[2] ROSA A. On certain valuation of the vertices of a graph［J］.Theory of Graphs， 1967：349-355.

[3] MACDOUGALL J A， MILLER M， WALLIS W D. Vertex-magic total labeling of graphs［J］. Utilitas Mathematics， 2002， 61： 3-21.

[4] ZHANG Z F， CHEN X E， LI J W， et al. On adjacent vertex distinguishing total coloring of graphs［J］. Science in China Ser A： Mathematics， 2005， 48（3）： 289-299.

[5] 奚悦.若干图标号问题的研究［D］. 大连：大连理工大学，2007.

[6] XI Y. The research on labeling problems in graph［D］. Dalian：Dalian University of Technology， 2007. （Ch）.

[7] LI J W， ZHANG Z F， ZHU E Q， et al. Adjacent vertex reducible edge-total coloring of graphs［C/OL］//2009 2nd International Conference on Biomedical Engineering and Informatics. IEEE， 2009［2024-06-20］.

[8] 张树成.随机图的和可约染色与可约标号算法研究［D］. 兰州：兰州交通大学，2022.

[9] ZHANG S C. Research on sum reducible coloring and reducible labeling algorithms of random graphs［D］. Lanzhou：Lanzhou Jiaotong University， 2022. （Ch）.

[10] 王丽，李敬文，杨文珠，等.单圈图的邻点可约全标号［J］.山东大学学报（理学版），2024，59（6）：45-55.

[11] WANG L， LI J W， YANG W Z， et al. Adjacent vertex reducible total labeling of unicyclic graphs［J］. Journal of Shandong University （Natural Science）， 2024，59（6）：45-55. （Ch）.

[12] 刘家保，王林，陆一南.具有公共边的双圈图的奇优美标号及其算法［J］.合肥工业大学学报（自然科学版），2012，35（6）：857-859.

[13] LIU J B， WANG L， LU Y N. Odd graceful labeling and algorithm of bicyclic graphs with a common edge［J］. Journal of Hefei University of Technology（Natural Science），2012，35（6）：857-859. （Ch）.

[14] 刘家保，王林，陆一南.双圈图 G n , m 的奇优美标号及其算法［J］.合肥工业大学学报（自然科学版），2012，35（5）：708-710.

[15] LIU J B， WANG L， LU Y N. Odd graceful labeling and algorithm of double-cycles graphs G n , m ［J］. Journal of Hefei University of Technology（Natural Science），2012，35（5）：708-710. （Ch）.

[16] 罗榕，李敬文，张树成，等.若干联图的邻点和可约边染色［J］.华中师范大学学报（自然科学版），2023，57（2）：201-207.

[17] LUO R， LI J W， ZHANG S C， et al. Adjacent points sum reducible edge coloring of some joint graphs［J］. Journal of Central China Normal University（Natural Sciences），2023，57（2）：201-207. （Ch）.

[18] 李敬文，康玉梅，张树成，等.图的点和可约边染色［J］.武汉大学学报（理学版），2022，68（5）：487-495.

[19] LI J W， KANG Y M， ZHANG S C， et al. The vertex sum reducible edge coloring for graphs［J］. Journal of Wuhan University （Natural Science Edition），2022，68（5）：487-495. （Ch）.

基金资助

国家自然科学基金项目(11961041)

国家自然科学基金项目(62262038)

甘肃省自然科学基金重点项目(24JRRA222)

甘肃省媒体融合技术与传播重点实验室项目(21ZD8RA008)