双圈图的邻点可约全标号

摘要

图G(V,E)的邻点可约全标号(adjacent vertex reducible total labeling, AVRTL)是一个从V(G)∪E(G)到连续整数集{1,2,…,|V(G)|+|E(G)|}的双射，且图中所有相邻同度顶点的标号之和均相同，为■.该文结合现实问题，借鉴传统遗传算法、蜂群算法等智能算法思路，设计了一种新型的AVRTL算法，通过预处理函数、调整函数等，利用循环迭代寻优的方式得到有限点内所有双圈图的邻点可约全标号结果.对实验结果进行分析，发现几类图的标号规律，总结得到若干定理并给出证明，最后给出猜想：所有的双圈图均为AVRTL图.

关键词

双圈图 / 邻点可约全标号 / 算法 / 图标号

基金资助

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