若干特殊图及其联图的邻点可约边标号算法

Algorithm for Adjacent Vertex Reducible Edge Labeling of Some Special Graphs and Their Associated Graphs

摘要

设G(V,E)是一个简单图，若存在一一映射f:E\left(G\right)\to \{\mathrm{1,2},\dots ,|E|\}，使得对任意两点uv\in E(G)，如果d(u)=d(v)，有S\left(u\right)=S(v)，其中S\left(u\right)=\sum _{uw\in E(G)}f(uw)，d(u)表示点u的度，则称f为G的邻点可约边标号（adjacent vertex reducible edge labeling，AVREL）。在已有图标号概念与可约染色概念的基础之上，结合实际问题提出了邻点可约边标号新概念，并设计了一种新的邻点可约边标号算法（简称AVREL算法）。该算法对边初始标号，然后针对邻点可约边标号的解空间进行递归搜索，最终筛选出满足边标号的图集并以标号矩阵的形式输出。经过对算法结果分析，总结出若干路图、扇图、星图、轮图、树图等特殊图及其联图在不同情况下的邻点可约边标号定理，并给出了证明。

Abstract

Let G(V,E) be a simple graph,if there is a one-to-one mapping f:E\left(G\right)\to \{\mathrm{1,2},\dots ,|E|\},so that for any two points,if d(u)=d(v),there is S\left(u\right)=S(v),where S\left(u\right)=\sum _{uw\in E(G)}f(uw),d(u) represents the degree of the point u,thenfis the Adjacent Vertex Reducible Edge Labeling (AVREL).Based on the existing graph labeling concept and the reducible concept, this paper proposes a new concept of Adjacent Vertex Reducible Edge labeling combined with practical problems, and designs a new type of Adjacent Vertex Reducible Edge Labeling algorithm (referred to as AVREL algorithm).The algorithm uses the initial label of the edge, and then searches the solution space of the label of the atlas, and finally filters out the atlas that meets the label of the edge and outputs it in the form of a label matrix. After analyzing the results of the algorithm, we summarize several special graphs such as fan graphs, star graphs, wheel graphs, and their associated graphs under different conditions, and gave proofs for the adjacent vertex reducible edge labeling theorems.

Graphical abstract

关键词

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

Key words

special graph / associated graph / adjacent vertex reducible edge labeling / labeling algorithm

0　 引 言

图的标号作为图论中一个分支，具有重要的理论研究意义与现实意义。现实生活中的很多问题都可以转换为图标号问题来解决，比如通信段的频率分配问题、图形密码资源分配和交通调度等。图标号概念最早在1967年由\mathrm{R}\mathrm{o}\mathrm{s}\mathrm{a}等^[1]提出优美猜想，即“每一棵树都是优美的”，在优美猜想的基础上有学者提出了优美标号以及后来的顶点魔幻标号^[2，3]。2009年，文献[4]提出了图的可约染色系列概念。

本文提出的邻点可约边标号新概念就是在图的顶点魔幻全标号与图的邻点可约边染色^[5~7]概念基础上产生的。我们利用蜂群算法^[8]、遗传算法等随机搜索算法的设计思路设计了可以解决特殊图及其联图的邻点可约边标号的算法，分析了算法得到的标号结果，总结了几种图类的若干定理并进行了证明。

1　 预备知识

本文主要讨论的是路、星、扇、轮、树等特殊图^[9]及其联图的邻点可约边标号。

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

定义2^[3] 风筝图(\mathrm{K}\mathrm{i}\mathrm{t}\mathrm{e})：\left(n,t\right)⁃K是包含一个顶点为n的圈图C_n和长度为t路图P_t组成的图。

定义3 若一个树图除了叶子节点外其他节点的度都相同，则这类图称为T_n图（如图1所示）。

定义4 联图S_m^{F_n}(m\ge \mathrm{2},n\ge \mathrm{4})（如图2）,设S_m的点集为V=\{w_{\mathrm{0}},w_{\mathrm{1}},\dots ,w_m\}，m个F_n的点集为V=V\left(\mathrm{1}{F}_n\right)\bigcup V\left(\mathrm{2}{F}_n\right)\bigcup \cdots \bigcup V\left(m{F}_n\right)=\{\mathrm{1}{u}_{\mathrm{0}},\mathrm{1}{u}_{\mathrm{1}},\dots ,\mathrm{1}{u}_n\cup \mathrm{2}{u}_{\mathrm{0}},\mathrm{2}{u}_{\mathrm{1}},\dots ,\mathrm{2}{u}_n\bigcup \cdots \bigcup h{u}_{\mathrm{0}},h{u}_{\mathrm{1}},\dots ,h{u}_n\}，其中w_{\mathrm{1}}=\mathrm{1}{u}_{\mathrm{0}},w_{\mathrm{2}}=\mathrm{2}{u}_{\mathrm{0}},\cdots ,w_m=h{u}_{\mathrm{0}}。

2　 AVREL算法

根据邻点可约边标号的定义，将所有图分为两类，一类是具有相邻同度点的图，一类不存在相邻同度点的图。本文设置有一个图分类函数\mathrm{C}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{f}\mathrm{y}，一个在搜索解空间的过程中判断是否满足标号条件的函数\mathrm{i}\mathrm{s}\mathrm{B}\mathrm{a}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}。最终标号成功的状态是指相邻同度点的标号和相等并且满足标号数连续的状态。

AVREL算法的思想是将图的邻接矩阵改造为满足AVREL要求的初始标号矩阵，通过分类函数筛选出具有相邻同度点的图集，然后针对邻点可约边标号的解空间进行递归搜索，利用平衡算子判断标号矩阵是否处于平衡状态，最终筛选出满足邻点可约边标号的图集，并以标号矩阵的形式输出。

3　 定理及证明

定理1 扇图F_n(n\ge \mathrm{3})是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

证 设F_n的顶点集为\{u_{\mathrm{0}},u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n\}。其中u_{\mathrm{0}}表示扇心，u_{\mathrm{1}}和u_n表示扇图的两个2度点。

(1) 当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，扇图F_n的邻点可约边标号为：

f\left(u_{\mathrm{0}}{u}_i\right)=\mathrm{2}i-\mathrm{1},i=\mathrm{1,2},\dots ,n;

\begin{array}{l}f\left(u_i{u}_{i+\mathrm{1}}\right)=\left\{\begin{array}{c}\mathrm{2}n-\mathrm{1}-i,i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\\ n+\mathrm{1}-i,i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\end{array}\right.,\\ i=\mathrm{1,2},\dots ,n-\mathrm{1};\end{array}

此时u_{\mathrm{1}}与u_n虽然是同度点，但并不相邻，所以只需考虑其他相邻的三度点满足标号和相同即可。点u_{\mathrm{2}},u_{\mathrm{3}},\cdots ,u_{n-\mathrm{1}}均为三度点，当\mathrm{2}\le i\le n-\mathrm{1}时，\mathrm{S}\mathrm{u}\mathrm{m}(u_i)=f(u_{\mathrm{0}}{u}_i)+f(u_{i-\mathrm{1}}{u}_i)+f(u_i{u}_{i+\mathrm{1}})=\mathrm{2}i-\mathrm{1}+\mathrm{2}n-\mathrm{1}-i+\mathrm{1}+n+\mathrm{1}-i=\mathrm{3}n。因此图中所有的相邻三度点的标号和都是相同的，其他的点不用考虑，所以当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，扇图F_n是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

(2) 当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，F_n的邻点可约边标号为

f\left(u_{\mathrm{0}}{u}_i\right)=\mathrm{2}i,i=\mathrm{1,2},\dots ,n-\mathrm{1};

f\left(u_{\mathrm{0}}{u}_n\right)=\mathrm{2}n-\mathrm{1};

\begin{array}{l}f\left(u_i{u}_{i+\mathrm{1}}\right)=\left\{\begin{array}{ll}n-i,& i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\\ \mathrm{2}n-\mathrm{1}-i,& i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\end{array}\right.,\\ i=\mathrm{1,2},\dots ,n-\mathrm{1};\end{array}

同理可知当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)，\mathrm{2}\le i\le n-\mathrm{1}时，\mathrm{S}\mathrm{u}\mathrm{m}(u_i)=f(u_{\mathrm{0}}{u}_i)+f(u_{i-\mathrm{1}}{u}_i)+f(u_i{u}_{i+\mathrm{1}})=\mathrm{3}n，因为图中只有三度点存在相邻的情况，所以只需要考虑三度点即可，其他度的点都是没有关联的，故当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，扇图F_n是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

由(1)，(2)两种情形可知，当n\ge \mathrm{3}时，扇图F_n是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

部分扇图标号结果如图3所示。

定理2 联图F_n\uparrow P_{\mathrm{2}}(n\ge \mathrm{3})是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

证 设F_n的顶点集为\{u_{\mathrm{0}},u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n\}。其中u_{\mathrm{0}}表示扇心，联图F_n\uparrow P_{\mathrm{2}}表示一条P_{\mathrm{2}}连接在扇图的扇心上。

(1) 当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)，F_n\uparrow P_{\mathrm{2}}的\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}标号为：

f\left(u_{\mathrm{0}}{u}_i\right)=\mathrm{2}i-\mathrm{1},i=\mathrm{1,2},\dots ,n;

f\left(u_{\mathrm{0}}{v}_{\mathrm{1}}\right)=\mathrm{2}n;

\begin{array}{l}f\left(u_i{u}_{i+\mathrm{1}}\right)=\left\{\begin{array}{cc}\mathrm{2}n-\mathrm{1}-i,& i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\\ n+\mathrm{1}-i,& i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\end{array}\right.,\\ i=\mathrm{1,2},\dots ,n-\mathrm{1}\end{array};

F_n\uparrow P_{\mathrm{2}}中只存在相邻的三度点，u_{\mathrm{1}}与u_n虽然都是二度点但不相邻，u_{\mathrm{0}}是独度点，所以这三个点不用考虑，只需要保证相邻的三度点标号和相同即可。点u_{\mathrm{2}},u_{\mathrm{3}},\cdots ,u_{n-\mathrm{1}}均为三度点，当\mathrm{2}\le i\le n-\mathrm{1}时，\mathrm{S}\mathrm{u}\mathrm{m}(u_i)=f(u_{\mathrm{0}}{u}_i)+f(u_{i-\mathrm{1}}{u}_i)+f(u_i{u}_{i+\mathrm{1}})=\mathrm{2}i-\mathrm{1}+\mathrm{2}n-\mathrm{1}-i+\mathrm{1}+n+\mathrm{1}-i=\mathrm{3}n，所以当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)，F_n\uparrow P_{\mathrm{2}}是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)，F_n\uparrow P_{\mathrm{2}}的\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}标号为

f\left(u_{\mathrm{0}}{u}_i\right)=\mathrm{2}i,i=\mathrm{1,2},\dots ,n-\mathrm{1};

f\left(u_{\mathrm{0}}{u}_n\right)=\mathrm{2}n-\mathrm{1};

f\left(u_{\mathrm{0}}{v}_{\mathrm{1}}\right)=\mathrm{2}n;

\begin{array}{l}f\left(u_i{u}_{i+\mathrm{1}}\right)=\left\{\begin{array}{ll}n-i,& i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\\ \mathrm{2}n-\mathrm{1}-i,& i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\end{array},\right.\\ i=\mathrm{1,2},\dots ,n-\mathrm{1};\end{array}

同理可知当\mathrm{2}\le i\le n-\mathrm{1}时，\mathrm{S}\mathrm{u}\mathrm{m}(u_i)=f(u_{\mathrm{0}}{u}_i)+f(u_{i-\mathrm{1}}{u}_i)+f(u_i{u}_{i+\mathrm{1}})=\mathrm{2}i+n-i+\mathrm{1}+\mathrm{2}n-\mathrm{1}-i=\mathrm{3}n，所以当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)，F_n\uparrow P_{\mathrm{2}}也是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

由(1)与(2)两种情况可知，当n\ge \mathrm{3}时，联图F_n\uparrow P_{\mathrm{2}}是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

部分联图F_n\uparrow P_{\mathrm{2}}标号结果如图4所示。

定理3 轮图W_n(n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right),n\ge \mathrm{4})满足AVREL图。

证 设轮图W_n的顶点集为\{u_{\mathrm{0}},u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n\}, u_{\mathrm{0}}为W_n的中心节点。

当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right),W_n(n\ge \mathrm{4})的AVREL标号为

f\left(u_{\mathrm{0}}{u}_i\right)=\mathrm{2}n-i+\mathrm{1},i=\mathrm{1,2},\dots ,n;

f\left(u_n{u}_{\mathrm{1}}\right)=(n+\mathrm{1})/\mathrm{2}；

\begin{array}{l}f\left(u_i{u}_{i+\mathrm{1}}\right)=\left\{\begin{array}{ll}(i+\mathrm{1})/\mathrm{2},& i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\\ (n+i+\mathrm{1})/\mathrm{2},& i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\end{array},\right.\\ i=\mathrm{1},\dots ,n-\mathrm{1}\end{array}

由于轮图中只存在三度点和独度点u_{\mathrm{0}}，并且三度点均满足相邻的条件，所以可以不用考虑独度点u_{\mathrm{0}}，只需要让三度点满足标号和相同即可。其中u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n均为三度点，当\mathrm{2}\le i\le n-\mathrm{1}时，\mathrm{S}\mathrm{u}\mathrm{m}(u_i)=f(u_{\mathrm{0}}{u}_i)+f(u_{i-\mathrm{1}}{u}_i)+f(u_i{u}_{i+\mathrm{1}})=\mathrm{2}n-i+\mathrm{1}+(i-\mathrm{1}+\mathrm{1})/\mathrm{2}+(n+i+\mathrm{1})/\mathrm{2}=(\mathrm{5}n+\mathrm{3})/\mathrm{2}，所以当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)，W_n是AVREL图。

部分轮图W_n的标号结果如图5所示。

猜测1 当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时,W_n(n\ge \mathrm{4})也是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

部分轮图W_n(n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right))的标号结果如图6所示。

定理4 联图W_n\downarrow P_{\mathrm{2}}满足\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

证 设W_n\downarrow P_{\mathrm{2}}的顶点集为\{u_{\mathrm{0}},u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n,u_{n+\mathrm{1}}\}，其中P_{\mathrm{2}}连接于W_n的任意非中心顶点构成的图。

当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，部分W_n\downarrow P_{\mathrm{2}}标号结果如图7所示。W_n\downarrow P_{\mathrm{2}}\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}标号为：

f\left(u_n{u}_{n+\mathrm{1}}\right)=\mathrm{2}n+\mathrm{1};

f\left(u_n{u}_{\mathrm{1}}\right)=\mathrm{2}n;

f\left(u_{\mathrm{0}}{u}_i\right)=i,i=\mathrm{1,2},\dots ,n;

f\left(u_i{u}_{i+\mathrm{1}}\right)=\left\{\begin{array}{ll}\mathrm{2}n-\frac{i}{\mathrm{2}},& i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right),n-\mathrm{2}\ge i\ge \mathrm{2}\\ \frac{\mathrm{3}n}{\mathrm{2}}-\frac{i-\mathrm{1}}{\mathrm{2}},& i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right),n-\mathrm{1}\ge i\ge \mathrm{1}\end{array}\right.；

此时，点u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_{n-\mathrm{1}}为图中所有度为3的点，其标号和为\mathrm{S}\mathrm{u}\mathrm{m}(u_i)=f(u_{\mathrm{0}}{u}_i)+f(u_i{u}_{i+\mathrm{1}})+f(u_{i-\mathrm{1}}{u}_i)=i+(\frac{\mathrm{3}n}{\mathrm{2}}-\frac{i-\mathrm{1}}{\mathrm{2}})+(\mathrm{2}n-\frac{i-\mathrm{1}}{\mathrm{2}})=\frac{\mathrm{7}n}{\mathrm{2}}+\mathrm{1},i=\mathrm{2,3},\cdots ,n-\mathrm{1}。可知，图中所有度为3的点的标号和相同。点u_{\mathrm{0}},u_n和u_{n+\mathrm{1}}分别为图中度为n(n\ge \mathrm{6})，4和1的点，与其他点的度互不相同，所以不用考虑其标号和。因此，当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)(n\ge \mathrm{6})时，联图W_n\downarrow P_{\mathrm{2}}是AVREL图。

当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，部分W_n\downarrow P_{\mathrm{2}}标号结果如图8所示。

W_n\downarrow P_{\mathrm{2}}邻点可约边标号为：

f\left(u_n{u}_{n+\mathrm{1}}\right)=\mathrm{2}n+\mathrm{1};

f\left(u_n{u}_{\mathrm{1}}\right)=\mathrm{2}n;

f\left(u_{\mathrm{0}}{u}_i\right)=i,i=\mathrm{1,2},\dots ,n;

f\left(u_i{u}_{i+\mathrm{1}}\right)=\left\{\begin{array}{ll}\mathrm{2}n-\frac{i}{\mathrm{2}},& i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right),n-\mathrm{1}\ge i\ge \mathrm{2}\\ \frac{\mathrm{3}n-\mathrm{1}}{\mathrm{2}}-\frac{i-\mathrm{1}}{\mathrm{2}},& i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right),n-\mathrm{2}\ge i\ge \mathrm{1}\end{array};\right.

此时，点u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_{n-\mathrm{1}}为图中所有度为3的点，其标号和为\mathrm{S}\mathrm{u}\mathrm{m}(u_i)=f(u_{\mathrm{0}}{u}_i)+f(u_i{u}_{i+\mathrm{1}})+f(u_{i-\mathrm{1}}{u}_i)=i+(\frac{\mathrm{3}n-\mathrm{1}}{\mathrm{2}}-\frac{i-\mathrm{1}}{\mathrm{2}})+(\mathrm{2}n-\frac{i-\mathrm{1}}{\mathrm{2}})=\frac{\mathrm{7}n-\mathrm{1}}{\mathrm{2}}+\mathrm{1},i=\mathrm{2,3},\cdots ,n-\mathrm{1}\mathrm{。}可知，图中所有度为3的点的标号和相同。点u_{\mathrm{0}},u_n和u_{n+\mathrm{1}}分别为图中度为n(n\ge \mathrm{5})，4和1的点，与其他点的度互不相同，所以不用考虑其标号和。因此，当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)(n\ge \mathrm{5})时，联图W_n\downarrow P_{\mathrm{2}}是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

综合(1)，(2)两种情形，可得当n\ge \mathrm{5}时，联图W_n\downarrow P_{\mathrm{2}}为\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

定理5 广义太阳图C_n^{P_{\mathrm{2}}}(n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right),n\ge \mathrm{3})是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

证 广义太阳图C_n^{P_{\mathrm{2}}}(n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right))的顶点集为\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n,v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_n\}，其中P_{\mathrm{2}}连接在圈图的每一个点上。

当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)，广义太阳图C_n^{P_{\mathrm{2}}}的邻点可约边标号

f(u_i{v}_i)=\mathrm{2}n-i+\mathrm{1},(n\ge j\ge i\ge \mathrm{1});

当i(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})==\mathrm{1}时

f(u_i{u}_{i+\mathrm{1}})=(i+\mathrm{1})/\mathrm{2},i=\mathrm{1,2},\mathrm{3},\cdots ,n-\mathrm{1};

f(u_n{u}_{\mathrm{1}})=f(u_{n-\mathrm{2}}{u}_{n-\mathrm{1}})+\mathrm{1};

当i(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})==\mathrm{0}时

f(u_i{u}_{i+\mathrm{1}})=f(u_n{u}_{\mathrm{1}})+(i/\mathrm{2});

此时图中只存在1度点和3度点，由于1度点都是不相邻的，所以不需要考虑，只需要保证相邻的3度点标号和相同即可。图中u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n均为3度点且相邻，当\mathrm{2}\le i\le n-\mathrm{1}时，\mathrm{S}\mathrm{u}\mathrm{m}(u_i)=f(u_{i-\mathrm{1}}{u}_i)+f(u_i{u}_{i+\mathrm{1}})+f(u_i{v}_i)=f(u_{\mathrm{1}}{u}_{\mathrm{2}})+f(u_n{u}_{\mathrm{1}})+f(u_{\mathrm{1}}{v}_{\mathrm{1}})=\mathrm{1}+\mathrm{2}n+(n+\mathrm{1})/\mathrm{2}=(\mathrm{5}n+\mathrm{3})/\mathrm{2}。因此当(n\equiv\mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}))时，广义太阳图C_n^{P_{\mathrm{2}}}是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

部分广义太阳图C_n^{P_{\mathrm{2}}}的标号结果如图9所示。

根据AVREL算法得到的广义太阳图的标号结果，给出以下的猜测：

猜测2 当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时,广义太阳图C_n^{P_{\mathrm{2}}}(n\ge\mathrm{3})也是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

给出部分n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时,C_n^{P_{\mathrm{2}}}图的部分标号结果，如图10所示。

定理6 联图S_m^{F_n}(m\ge \mathrm{2},n\ge \mathrm{3},m!=n+\mathrm{1})是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

证 （1） 当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，联图S_m^{F_n}的邻点可约边标号为

f\left(w_{\mathrm{0}}{w}_i\right)=\mathrm{2}hn,h=i=\mathrm{1,2},\cdots ,n;

\begin{array}{l}f\left(h{u}_{\mathrm{0}}h{u}_i\right)=\mathrm{2}i-\mathrm{1}+\mathrm{2}(h-\mathrm{1})n,\\ h=\mathrm{1,2},\mathrm{3},\cdots ,m;i=\mathrm{1,2},\cdots ,n;\end{array}

f\left(h{u}_{i}h{u}_{i+\mathrm{1}}\right)=

\left\{\begin{array}{c}\begin{array}{ll}\mathrm{2}hn-\mathrm{1}-i,& h=\mathrm{1,2},\mathrm{3},\cdots ,m;i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\\ (\mathrm{2}h-\mathrm{1})n+\mathrm{1}-i,& h=\mathrm{1,2},\mathrm{3},\cdots ,m;i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\end{array}\end{array},\right.

i=\mathrm{1,2},\cdots ,n-\mathrm{1};

此时，图中存在1个m度点，\mathrm{2}m个不相邻的2度点，m个不相邻的n度点以及每个F_n存在相邻的三度点，所以只需要保证每个F_n的三度点标号和相同即可。当\mathrm{2}\le i\le n-\mathrm{1}时,\mathrm{S}\mathrm{u}\mathrm{m}(h{u}_i)=f(h{u}_{i-\mathrm{1}}h{u}_i)+f(h{u}_{i}h{u}_{i+\mathrm{1}})+f(h{u}_{\mathrm{0}}h{u}_i)=\mathrm{2}hn-\mathrm{1}-i+\mathrm{1}+\mathrm{2}hn-n+\mathrm{1}-i+\mathrm{2}i-\mathrm{1}+\mathrm{2}hn-\mathrm{2}n=(\mathrm{6}h-\mathrm{3})n。所以当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，联图S_m^{F_n}是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

（2） 当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，联图S_m^{F_n}的邻点可约边标号为

f\left(w_{\mathrm{0}}{w}_i\right)=\mathrm{2}hn-\mathrm{1},h=i=\mathrm{1,2},\cdots ,n;

\begin{array}{l}f\left(h{u}_{\mathrm{0}}h{u}_i\right)=\mathrm{2}i+\mathrm{2}(h-\mathrm{1})n,\\ h=\mathrm{1,2},\mathrm{3},\cdots ,m;i=\mathrm{1,2},\cdots ,n;\end{array}

f\left(h{u}_{i}h{u}_{i+\mathrm{1}}\right)=

\left\{\begin{array}{c}(\mathrm{2}h-\mathrm{1})n-i,h=\mathrm{2,3},\cdots ,m;i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\\ \mathrm{2}hn-\mathrm{1}-i,h=\mathrm{1,2},\mathrm{3},\cdots ,m;i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\end{array},\right.

i=\mathrm{1,2},\cdots ,n-\mathrm{1};

同理可知，当\mathrm{2}\le i\le n-\mathrm{1}时，\mathrm{S}\mathrm{u}\mathrm{m}(h{u}_i)=f(h{u}_{i-\mathrm{1}}h{u}_i)+f(h{u}_{i}h{u}_{i+\mathrm{1}})+f(h{u}_{\mathrm{0}}h{u}_i)=\mathrm{2}hn-n-i+\mathrm{1}+\mathrm{2}hn-\mathrm{1}-i+\mathrm{2}i+\mathrm{2}hn-\mathrm{2}n=(\mathrm{6}h-\mathrm{3})n。所以当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，联图S_m^{F_n}也是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

由(1)，(2)可知，当m\ge \mathrm{2},n\ge \mathrm{3},m!=n+\mathrm{1}时，联图S_m^{F_n}是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

联图S_{\mathrm{3}}^{F_{\mathrm{5}}},S_{\mathrm{4}}^{F_{\mathrm{6}}}的标号结果如图11所示。

定理7 联图F_n\downarrow (\mathrm{3,3})⁃K(n\ge \mathrm{3},n!=\mathrm{4})是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

设F_n的点集V=\{w_{\mathrm{0}},w_{\mathrm{1}},\dots ,w_n\}，(\mathrm{3,3})⁃K的点集为V=V(C_{\mathrm{3}})\bigcup V(P_{\mathrm{3}})=\{u_{\mathrm{1}},u_{\mathrm{2}},u_{\mathrm{3}}\}\bigcup \{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}}\}，其中u_n=u_{\mathrm{3}},u_{\mathrm{1}}=v_{\mathrm{3}}。

证 （1） 当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，F_n\downarrow (\mathrm{3,3})⁃K的邻点可约边标号为

f\left(w_{\mathrm{0}}{w}_i\right)=\mathrm{2}i-\mathrm{1},i=\mathrm{1,2},\cdots ,n;

\begin{array}{l}f\left(w_i{w}_{i+\mathrm{1}}\right)=\left\{\begin{array}{c}\mathrm{2}n-i-\mathrm{1},i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\\ n-i+\mathrm{1},i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\end{array}\right.,\\ i=\mathrm{1,2},\cdots ,n-\mathrm{1};\end{array}

f\left(u_i{u}_{i+\mathrm{1}}\right)=\mathrm{2}n+i-\mathrm{1},i=\mathrm{1,2},\mathrm{3};

f\left(u_{\mathrm{1}}{u}_n\right)=\mathrm{2}n+\mathrm{2};

f\left(v_{\mathrm{1}}{v}_{\mathrm{2}}\right)=\mathrm{2}n+\mathrm{3};

f\left(v_{\mathrm{2}}{v}_{\mathrm{3}}\right)=\mathrm{2}n+\mathrm{4}；

此时图中只存在相邻的3度点，其他的n度点，1度点，均只有1个所以不用考虑，u_{\mathrm{1}}这个3度点与其他3度点不相邻，v_{\mathrm{1}}与u_{\mathrm{2}}虽然都是2度点，但不相邻，也不需要考虑。所以只保证w_{\mathrm{2}},w_{\mathrm{3}},\cdots ,w_{n-\mathrm{1}}这些3度点标号和相同即可。当\mathrm{2}\le i\le n-\mathrm{1}时，\mathrm{S}\mathrm{u}\mathrm{m}(w_i)=f(w_{i-\mathrm{1}}{w}_i)+f(w_i{w}_{i+\mathrm{1}})+f(w_{\mathrm{0}}{w}_i)=\mathrm{2}n-i+\mathrm{1}-\mathrm{1}+n-i+\mathrm{1}+\mathrm{2}i-\mathrm{1}=\mathrm{3}n。因此当n\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，联图F_n\downarrow (\mathrm{3,3})⁃K是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，F_n\downarrow (\mathrm{3,3})⁃K的邻点可约边标号为

f\left(w_{\mathrm{0}}{w}_i\right)=\mathrm{2}i,i=\mathrm{1,2},\cdots ,n-\mathrm{1};

f\left(w_{\mathrm{0}}{w}_n\right)=\mathrm{2}n-\mathrm{1};

\begin{array}{l}f\left(w_i{w}_{i+\mathrm{1}}\right)=\left\{\begin{array}{ll}n-i,& i\equiv \mathrm{1}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\\ \mathrm{2}n-i-\mathrm{1},& i\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)\end{array}\right.,\\ i=\mathrm{1,2},\cdots ,n-\mathrm{1};\end{array}

f\left(u_i{u}_{i+\mathrm{1}}\right)=\mathrm{2}n+i-\mathrm{1},i=\mathrm{1,2},\mathrm{3};

f\left(u_{\mathrm{1}}{u}_n\right)=\mathrm{2}n+\mathrm{2};

f\left(v_{\mathrm{1}}{v}_{\mathrm{2}}\right)=\mathrm{2}n+\mathrm{3};

f\left(v_{\mathrm{2}}{v}_{\mathrm{3}}\right)=\mathrm{2}n+\mathrm{4};

同理也可以得出当\mathrm{2}\le i\le n-\mathrm{1}时，\mathrm{S}\mathrm{u}\mathrm{m}(w_i)=f(w_{i-\mathrm{1}}{w}_i)+f(w_i{w}_{i+\mathrm{1}})+f(w_{\mathrm{0}}{w}_i)=\mathrm{3}n。因此当n\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}\right)时，联图F_n\downarrow (\mathrm{3,3})⁃K是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

由(1)，(2)可知，当n\ge \mathrm{5}时，F_n\downarrow (\mathrm{3,3})⁃K(n\ge \mathrm{4})是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

部分联图F_n\downarrow (\mathrm{3,3})⁃K的标号结果如图12所示。

定理8 树图T_n(\mathrm{3}\le n\le \mathrm{19})，是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

如表1所示，根据AVREL算法得到了\mathrm{3}\le n\le \mathrm{19}的树图的标号结果。

通过表1中的标号结果可以统计出在19个点之内的树图的标号情况，从这些满足标号的图集中，统计并总结出了T_n图在\mathrm{3}\le n\le \mathrm{19}时，是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

由表1数据可以得到树图中满足标号图所占的比例，如图13所示，我们可以看到在19个点以内的树图随着点数和边数的增加，相应点数和边数下满足标号的图所占的比例在变小。

部分T_{(n)}图的标号结果如图14所示。

根据算法得到的结果可以得出19个点以内的T_{(n)}图都是满足这个定理的。但由于机器算力以及算法效率的限制并未进行更大点数树图的实验，有以下猜测：

猜测3 当n\ge \mathrm{20}时，T_n图是\mathrm{A}\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{L}图。

4　 结 语

本文在已有图标号的概念基础上，提出了邻点可约边标号概念。通过借鉴已有智能算法设计出了一种新型启发式搜索算法，邻点可约边标号算法，针对有限点内的所有非同构图进行计算，经过对运算结果的分析总计，给出了若干定理和猜测。

参考文献

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

[2] BONDY J A， MURTY U S R. Graph Theory with Applications［M］. New York： American Elsevier Pub Co， 1976. DOI: 10.1007/978-1-349-03521-2 .

[3] MACDOUGALL J A， MILLER M， WALLIS W D. Vertex-magic total labelings of graphs ［J］. Utilitas Mathematics， 2002， 61： 3-21. DOI: 10.1007/978-1-4612-0123-6_3 .

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

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

[6] 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. DOI：10.14188/j.1671-8836.2020.0314（Ch ）.

[7] BURRIS A C， BACA M， MACDOUGALL J， et al. Vertex-antimagic total labelings of graphs ［J］. Discussiones Mathematicae Graph Theory，2003，23（1）： 67-83. DOI: 10.7151/dmgt.1186 .

[8] LI J W， WANG B M， GU Y B， et al. Super edge-magic total labeling of combination graphs ［J］. Engineering Letters， 2020， 28（2）：412-419.

[9] 孙帅，李敬文，袁清厚. 随机图的L（2，1）-标号混合人工蜂群算法 ［J］. 武汉大学学报（理学版）， 2021， 67（2）： 158-164. DOI：10.14188/j.1671-8836.2020.0200 .

[10] SUN S， LI J W， YUAN Q H. A hybrid artificial bee colony algorithm for L（2，1）-labelling of random graph ［J］. Journal of Wuhan University （Natural Science Edition）， 2021， 67（2）： 158-164. DOI：10.14188/j.1671-8836.2020.0200（Ch ）.

[11] 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. DOI: 10.1007/978-1-4612-0123-6_2 .

基金资助

国家自然科学基金(11961041)

国家自然科学基金(62062049)

甘肃省媒体融合技术与传播重点实验室开放课题(21ZD8RA008)