图 G(V,E)的邻点可约全标号(adjacent vertex reducible total labeling,AVRTL)是一个从V(G)U E(G)到连续整数集｛1,2,…,|V(G)|+|E(G)|｝的双射,且图中所有相邻同度顶点的标号之和均相同,为S(u)=f(u)+∑uw ∈ E(G)f(uw).该文结合现实问题,借鉴传统遗传算法、蜂群算法等智能算法思路,设计了一种新型的AVRTL算法,通过预处理函数、调整函数等,利用循环迭代寻优的方式得到有限点内所有双圈图的邻点可约全标号结果.对实验结果进行分析,发现几类图的标号规律,总结得到若干定理并给出证明,最后给出猜想:所有的双圈图均为AVRTL图.
Adjacent vertex reducible total labeling of bicyclic graphs
The adjacent vertex reducible total labeling(AVRTL)of a graph G(V,E)is a bijection from V(G)U 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(uww).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.
bicyclic graphadjacent vertex reducible total labelingalgorithmgraph labeling
万方数据
维普
