双圈图的邻点可约全标号  

Adjacent vertex reducible total labeling of bicyclic graphs

作　　者：王丽 李敬文[1] 宋晨 常文文 WANG Li;LI Jingwen;SONG Chen;CHANG Wenwen(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

机构地区：[1]兰州交通大学电子与信息工程学院,兰州730070

出　　处：《华中师范大学学报（自然科学版）》2024年第4期409-418,共10页Journal of Central China Normal University：Natural Sciences

基　　金：国家自然科学基金项目(11961041,62262038);甘肃省媒体融合技术与传播重点实验室项目(21ZD8RA008).

摘　　要：图G(V,E)的邻点可约全标号(adjacent vertex reducible total labeling,AVRTL)是一个从V(G)∪E(G)到连续整数集{1,2,…,|V(G)|+|E(G)|}的双射,且图中所有相邻同度顶点的标号之和均相同,为S(u)=f(u)+∑uw∈E(G)f(uw).该文结合现实问题,借鉴传统遗传算法、蜂群算法等智能算法思路,设计了一种新型的AVRTL算法,通过预处理函数、调整函数等,利用循环迭代寻优的方式得到有限点内所有双圈图的邻点可约全标号结果.对实验结果进行分析,发现几类图的标号规律,总结得到若干定理并给出证明,最后给出猜想:所有的双圈图均为AVRTL图.The adjacent vertex reducible total labeling(AVRTL)of a graph G(V,E)is a bijection from V(G)∪E(G)to the set of consecutive integers{1,2,…,|V(G)|+|E(G)|},and the sum of the labels is the same for all adjacent vertices in the graph with the same degree,as S(u)=f(u)+∑uw∈E(G)f(uw).Combining with real-world problems,a new AVRTL algorithm is designed by drawing on the ideas of traditional intelligent algorithms such as the genetic algorithm and bee colony algorithm,which uses circular,iterative merit-seeking to obtain the adjacent vertex reducible total labeling results of all bicyclic graphs within a finite number of points by means of preprocessing functions and adjustment functions.By analyzing the experimental results,the labeling rules of several types of graphs were found,several theorems were summarized,and proofs were given.Finally,the conjecture was given that all bicyclic graphs are AVRTL graphs.

关 键 词：双圈图 邻点可约全标号 算法 图标号 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]