若干联图的邻点可约全标号

doi:10.6040/j.issn.1671-9352.0.2023.465

摘要/Abstract

摘要： 对于无向连通图G(V,E),若存在一个单映射f:V(G)∪E(G)→{1,2,…,|V|+|E|},如果uv∈E(G)且d(u)=d(v),有S(u)=S(v),其中S(u)=f(u)+∑f(uz), d(u)表示点u的度,则称f为G的邻点可约全标号(adjacent vertex reducible total labeling, AVRTL)。结合遗传算法和粒子群算法设计一种启发式搜索算法,可以判断有限点内随机图是否存在AVRTL。通过对实验结果分析,总结了若干联图的定理并给出证明。得到结论:如果子图G1和G2是AVRTL图,则图运算↑_ab具有封闭性,即联图G1↑_abG2亦为AVRTL图。

关键词: 联图, 邻点可约全标号, AVRTL图, 启发式搜索算法, 图运算

Abstract: For an undirected connected graph G(V,E), if there exists a single mapping f:V(G)∪E(G)→{1,2,…,|V|+|E|}, and conditions uv∈E(G) and d(u)=d(v) are satisfied, then there exists S(u)=S(v), where S(u)=f(u)+∑ holds. Let d(u) denote the degree of vertex u; thus, f is referred to as an adjacent vertex reducible total labeling(AVRTL)of G. This study combines genetic algorithms and particle swarm algorithms to design a heuristic search algorithm that can determine whether a random graph with a finite number of vertices contains an AVRTL. Through the analysis of experimental results, several theorems regarding linked graphs are summarized and proved. Finally, the following conclusion is drawn: if subgraphs G1 and G2 are AVRTL graphs, then the graph operation ↑ab exhibits closure, meaning the linked graph G1↑_abG2 is also an AVRTL graph.

Key words: joint graphs, adjacent vertex reducible total labeling, AVRTL graphs, heuristic search algorithms, graph operations

中图分类号:

O157.6

王江,李敬文,高鑫,孙亮晶. 若干联图的邻点可约全标号[J]. 《山东大学学报(理学版)》, 2025, 60(8): 57-67.

WANG Jiang, LI Jingwen, GAO Xin, SUN Liangjing. Adjacent vertex reducible total labeling of some joint graphs[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(8): 57-67.

参考文献

[1] RINGEL G. Problem 25 in theory of graphs and its applications [J]. Porc Symposium Smolenice, 1963:171-234.
[2] ROSA A. On certain valuations of the vertices of a graph[J]. Theory of Graphs, 1967:349-355.
[3] 赵科,李敬文,魏众德. 优雅图猜想[J]. 大连理工大学学报,2018,58(6):641-648. ZHAO Ke, LI Jingwen, WEI Zhongde. Conjecture of elegant graph[J]. Journal of Dalian University of Technology, 2018, 58(6): 641-648.
[4] 王笔美,李敬文,顾彦波,等. 单圈图的边幻和全标号[J]. 山东大学学报(理学版),2020,55(9):42-50. WANG Bimei, LI Jingwen, GU Yanbo, et al. Edge-magic total labeling of unicyclic graphs[J]. Journal of Shandong University(Natural Science), 2020, 55(9):42-50.
[5] 孙帅,李敬文,袁清厚. 随机图的L(2,1)-标号混合人工蜂群算法[J]. 武汉大学学报(理学版),2021,67(2):158-164. SUN Shuai, LI Jingwen, YUAN Qinghou. 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.
[6] 张荞君,李敬文,张树成,等. 随机图的邻点和可约边标号算法[J]. 武汉大学学报(理学版),2022,68(5):479-486. ZHANG Qiaojun, LI Jingwen, ZHANG Shucheng, et al. Adjacent vertex sum reducible edge labeling algorithm of the random graph [J]. Journal of Wuhan University(Natural Science Edition), 2022, 68(5):479-486.
[7] 兰琳钰,李敬文,张树成,等. 图的点可约全标号算法研究[J]. 山东大学学报(理学版),2023,58(11):135-146. LAN Linyu, LI Jingwen, ZHANG Shucheng, et al. Vertex reducible total labeling algorithm for graph[J]. Journal of Shandong University(Natural Science), 2023, 58(11):135-146.
[8] WANG L, LI J, SONG C, et al. Adjacent vertex reducible total labeling of corona graph[J]. Engineering Letters, 2023, 31(2):1-16.
[9] WANG L, LI J, ZHANG L. Adjacent vertex reducible total labeling of graphs[J]. IAENG International Journal of Computer Science, 2023, 50(2):715-726.
[10] 朱利娜,李敬文,孙帅. 几类联图的L(2,1)-边染色算法研究[J]. 山东大学学报(理学版),2023,58(8):63-72. ZHU Lina, Li Jingwen, SUN Shuai. L(2,1)-edge coloring algorithm for several kinds of composite graphs[J]. Journal of Shandong University(Natural Science), 2023, 58(8):63-72.
[11] 李敬文,贾西贝,董威,等. 图的邻点可区别全染色算法[J]. 山东大学学报(理学版),2015,50(2):14-21. LI Jingwen, JIA Xibei, DONG Wei, et al. The algorithm for adjacent-vertex-distinguishing total coloring of graphs[J]. Journal of Shandong University(Natural Science), 2015, 50(2):14-21.
[12] 王丽,李敬文,杨文珠,等.单圈图的邻点可约全标号[J]. 山东大学学报(理学版),2024,59(6):44-55. WANG Li, LI Jingwen, YANG Wenzhu, et al. Adjacent vertex reducible total labeling of unicyclic graphs[J]. Journal of Shandong University(Natural Science), 2024, 59(6):44-55.
[13] 孙慧,姚兵. 关于圈龙图的奇优雅性[J]. 大连理工大学学报,2017,57(5):531-536. SUN Hui, YAO Bing. On odd-elegant quality of cyclic-dragon graphs[J]. Journal of Dalian University of Technology, 2017, 57(5):531-536.
[14] 李敬文,邵淑宏,袁清厚,等.两类联图的边幻和全标号[J]. 南开大学学报(自然科学版),2021,54(6):68-74. LI Jingwen, SHAO Shuhong, YUAN Qinghou, et al. Edge-magic total labelling of two kinds for composite graphs [J]. Acta Scientiarum Naturalium Universitatis Nankaiensis, 2021, 54(6):68-74.
[15] 李敬文,兰琳钰,张树成,等. 若干特殊图及其联图的邻点可约边标号算法[J]. 武汉大学学报(理学版),2022,68(5):463-470. LI Jingwen, LAN Linyu, ZHANG Shucheng, et al. Algorithm for adjacent vertex reducible edge labeling of some special graphs and their associated graphs [J]. Journal of Wuhan University(Natural Science Edition), 2022, 68(5):463-470.
[16] LI J, ZHANG S, LUO R, et al. Algorithm for adjacent vertex sum reducible edge coloring of random graphs[J]. Engineering Letters, 2022, 30(2):1-7.
[17] 顾彦波,李敬文,火金萍等. 图(p≤9)的边幻和全标号[J]. 大连理工大学学报,2020,60(4):427-436. GU Yanbo, LI Jingwen, HUO Jinping, et al. Edge magic total labeling of graphs(p≤9)[J]. Journal of Dalian University of Technology, 2020, 60(4):427-436.
[18] 顾彦波,李敬文,邵淑宏,等. 非边幻和图的若干定理及证明[J]. 武汉大学学报(理学版),2020,66(3):237-243. GU Yanbo, LI Jingwen, SHAO Shuhong, et al. Some theorems and proofs of non-edge-magic total labeling graphs [J]. Journal of Wuhan University(Natural Science Edition), 2020, 66(3):237-243.
[19] 王笔美,李敬文,袁清厚. 图的(a,d)-边反幻点标号[J]. 南开大学学报(自然科学版),2021,54(4):50-57. WANG Bimei, LI Jingwen, YUAN Qinghou.(a,d)-edge-antimagic vertex labeling of graphs [J]. Acta Scientiarum Naturalium Universitatis Nankaiensis, 2021, 54(4):50-57.
[20] WANG B, LI J. Edge-magic total labeling algorithm of unicyclic graphs[J]. IAENG International Journal of Applied Mathematics, 2021, 51(4):1-10.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed