您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2023, Vol. 58 ›› Issue (11): 135-146.doi: 10.6040/j.issn.1671-9352.0.2022.278

•   • 上一篇    下一篇

图的点可约全标号算法研究

兰琳钰1(),李敬文1,*(),张树成1,张丽景2,申化玉1   

  1. 1. 兰州交通大学电子与信息工程学院，甘肃 兰州 730070
    2. 兰州石化职业技术大学信息处理与控制工程学院，甘肃 兰州 730060
  • 收稿日期:2022-05-11 出版日期:2023-11-20 发布日期:2023-11-07
  • 通讯作者: 李敬文 E-mail:1106375858@qq.com;lijingwen28@163.com
  • 作者简介:兰琳钰(1998—)，女，硕士研究生，研究方向为图论及其应用. E-mail: 1106375858@qq.com
  • 基金资助:
    国家自然科学基金资助项目(11961041);国家自然科学基金资助项目(62062049);甘肃省科技计划资助项目(21ZD8RA008)

Vertex reducibletotal labeling algorithm for graphs

Linyu LAN1(),Jingwen LI1,*(),Shucheng ZHANG1,Lijing ZHANG2,Huayu SHEN1   

  1. 1. School of Electronics and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
    2. School of Information Processing and Control Engineering, Lanzhou Petrochemical University of Vocational Technology, Lanzhou 730060, Gansu, China
  • Received:2022-05-11 Online:2023-11-20 Published:2023-11-07
  • Contact: Jingwen LI E-mail:1106375858@qq.com;lijingwen28@163.com

RichHTML

0

PDF (PC)

369

摘要：

对于无向连通图G(V, E)，若存在一个单射函数f: V(G)∪E(G)→{1, 2, …, |V|+|E|}，使得对图中所有度数相同的点及其关联边的标号和都有$\operatorname{Sum}(u)=f(u)+\sum\limits_{u v \in E(G)} f(u v)=K $，K为常数，称映射关系f为图的点可约全标号(vertex reducible total labeling, VRTL)。借助计算机的算法及优化点可约全标号的传统解空间的方式，设计点可约全标号算法，针对点可约全标号的解空间进行递归搜索，对有限点以内的连通图进行点全标号验证。通过观察有限点内图的标号规律，延展出能刻画无限点的同类图的标号规律，给出具有延展性的全标号定理及数学证明。

关键词: 图, 全标号, 可约全标号, 点可约全标号, 点可约全标号算法

Abstract:

For an undirected connected graph G(V, E), if there exists a injective function f: V(G)∪E(G)→{1, 2, …, |V|+|E|}, such that any edge $\operatorname{Sum}(u)=f(u)+\sum\limits_{u v \in E(G)} f(u v)=K $, K is a constant, where u is any vertex in G(p, q) with the same degree, then G(p, q) is a vertex reducible total labeling (VRTL) graph, and the injective function f is vertex reducible total labeling. By means of computer and the way of optimizing the solution space of the vertex reducible total labeling, the algorithm of the vertex reducible total labeling is designed, and the solution space of the vertex reducible total labeling is recursively searched. By observing the labeling law of graphs within finite vertices, the labeling law of graphs of the same kind that can describe infinite vertices is extended and the total labeling theorems with extensibility and mathematical proof are given.

Key words: graph, total labeling, reducible total labeling, vertex reducible total labeling, vertex reducible total labeling algorithm

中图分类号: 

  • O157.6

图1

广义太阳图CnP2"

图2

偶阶Cn(4≤n≤8)全标号结果的示例"

表1

图G(p, q)(p=q)的VRTL标号结果(3≤p≤9)"

图G(p, q)(p=q) 图总数 VRTL图个数 非VRTL图个数
(3, 3) 1 1 0
(4, 4) 2 2 0
(5, 5) 5 5 0
(6, 6) 13 13 0
(7, 7) 33 33 0
(8, 8) 89 89 0
(9, 9) 240 240 0

图3

部分单圈图G(p, q)(p=q)(3≤p≤9)全标号结果的示例"

表2

图G(p, q)(p=q－1)的VRTL标号结果(4≤p≤9)"

图G(p, q)(p=q－1) 图总数 VRTL图个数 非VRTL图个数
(4, 5) 1 1 0
(5, 6) 5 5 0
(6, 7) 19 19 0
(7, 8) 67 67 0
(8, 9) 236 236 0
(9, 10) 797 797 0

图4

部分双圈图G(p, q)(p=q－1) (4≤p≤9)全标号结果的示例"

1 RINGEL G. Problem 25 in theory of graphs and its application[C]//Proceedings of the Symposium, New York, US: Academic Press, 1963: 171-234.
2 MACDOUGALL J A , MILLER M , SLAMIN , W W D . Vertex-magic total labelings of graphs[J]. Utilitas Mathematica, 2002, 61, 3- 21.
3 BURRIS A C , SCHELP R H . Vertex-distinguishing proper edge-colorings[J]. Journal of Graph Theory, 1997, 26 (2): 73- 82.
doi: 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C
4 BALISTER P N , RIORDAN O M , SCHELP R H . Vertex-distinguishing edge colorings of graphs[J]. Journal of Graph Theory, 2003, 42 (2): 95- 109.
doi: 10.1002/jgt.10076
5 奚悦. 若干图标号问题的研究[D]. 大连: 大连理工大学, 2007.
XI Yue. Research on some labeling problems in graph theory[D]. Dalian: Dalian University of Technology, 2007.
6 ZHU Enqiang, ZHANG Zhongfu, WANG Zhiwen, et al. Adjacent vetex reducible vertex-total coloring of graphs[C]// 2009 International Conference on Computational Intelligence and Software Engineering, Wuhan: IEEE, 2009: 1-3.
7 LI Jingwen, ZHANG Zhongfu, ZHU Enqiang, et al. Adjacent vertex reducible edge-total coloring of graphs[C]//2009 2nd International Conference on Biomedical Engineering and Informatics. New York: IEEE, 2009: 1-3.
8 李小慧. 随机图的可约染色算法研究[D]. 兰州: 兰州交通大学, 2015.
LI Xiaohui. Research on reducible coloring algorithm of random graph[D]. Lanzhou: Lanzhou Jiatong University, 2015.
9 席晓慧, 李敬文, 孙帅. 若干图的顶点魔幻全标号[J]. 西南师范大学学报(自然科学版), 2020, 45(8): 18-24.
XI Xiaohui, LI Jingwen, SUN Shuai. Journal of Southwest Normal University(Natural Science Edition), 2020, 45(8): 18-24.
10 李敬文, 康玉梅, 张树成, 等. 图的点和可约边染色[J]. 武汉大学学报(理学版), 2022, 68 (5): 478- 459.
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): 478- 459.
11 贾秀卿, 李沐春. 单圈图的D(2)-点可区别边染色[J]. 吉林大学学报(理学版), 2021, 59 (4): 807- 815.
JIA Xiuqing , LI Muchun . D(2)-vertex-distinguishing edge coloring of unicyclic graphs[J]. Journal of Jilin University(Science Edition), 2021, 59 (4): 807- 815.
12 罗榕, 李敬文, 张树成, 等. 若干联图的邻点和可约边染色[J]. 华中师范大学学报(自然科学版), 2023, 57 (2): 201- 207.
LUO Rong , LI Jingwen , ZHANG Shucheng , et al. Adjacent points sum reducible edge coloring of some joint graphs[J]. Journal of Central China Normal University (Natural Science Edition), 2023, 57 (2): 201- 207.
13 王树禾. 图论及其算法[M]. 合肥: 中国科学技术大学出版社, 1990.
WANG Shuhe . Graph theory and its algorithm[M]. Hefei: University of Science and Technology of China Press, 1990.
14 徐俊明. 图论及其应用[M]. 合肥: 中国科学技术大学出版社, 1998.
XU Junming . Graph theory and its application[M]. Hefei: University of Science and Technology of China Press, 1998.
15 WEST D B . Introduction to graph theory[M]. Upper Saddle River: Prentice Hall, 2001.
16 王亚茹, 姚兵. 关于太阳图奇偶可分的魔幻标号[J]. 东北师大学报(自然科学版), 2017, 49 (4): 10- 14.
WANG Yaru , YAO Bing . On the magic labeling divided into parity of Sun-graphs[J]. Journal of Northeast Normal University (Natural Science Edition), 2017, 49 (4): 10- 14.
17 徐喜荣. 图的标号问题的研究[D]. 大连: 大连理工大学, 2006.
XU Xirong. Research on labeling problems in graph theory[D]. Dalian: Dalian University of Technology, 2006.
[1] 李程,车文刚,高盛祥. 一种用于航拍图像的目标检测算法[J]. 《山东大学学报(理学版)》, 2023, 58(9): 59-70.
[2] 那宇嘉,谢珺,杨海洋,续欣莹. 融合上下文的知识图谱补全方法[J]. 《山东大学学报(理学版)》, 2023, 58(9): 71-80.
[3] 苏宇源,魏宗田,王艳. 图的p-边邻域离散数[J]. 《山东大学学报(理学版)》, 2023, 58(8): 57-62.
[4] 孙情,杨刚. 线性箭图的Gorenstein AC-表示[J]. 《山东大学学报(理学版)》, 2023, 58(8): 48-56.
[5] 高琦,戴洪帅,武艳华. 基于MPEWMA控制图的串联排队网络的监测与控制[J]. 《山东大学学报(理学版)》, 2023, 58(8): 104-110, 117.
[6] 朱利娜,李敬文,孙帅. 几类联图的L(2, 1)-边染色算法研究[J]. 《山东大学学报(理学版)》, 2023, 58(8): 63-72.
[7] 常乐,魏宗田. 基于邻域连通度优化的图的N[S]-T重构[J]. 《山东大学学报(理学版)》, 2023, 58(6): 40-45, 76.
[8] 尹会玲,陈京荣,苏晓艳. 星图与二部图的某些乘积图上的k-路点覆盖[J]. 《山东大学学报(理学版)》, 2023, 58(6): 18-24, 39.
[9] 汲颖,邓波,赵海兴,唐彦龙. 基于图运算下的控制熵[J]. 《山东大学学报(理学版)》, 2023, 58(12): 140-150.
[10] 王新生,朱小飞,李程鸿. 标签指导的多尺度图神经网络蛋白质作用关系预测方法[J]. 《山东大学学报(理学版)》, 2023, 58(12): 22-30.
[11] 夏龙苗,魏宗田,丁丽萍. 定向图的燃烧连通度[J]. 《山东大学学报(理学版)》, 2023, 58(12): 127-133.
[12] 李锦,徐常青. 不含相交三角形IC-可平面图的邻点可区别边染色[J]. 《山东大学学报(理学版)》, 2023, 58(12): 134-139.
[13] 韩慧,刘雨童,姚海元. 梯子图双强迫多项式的递推求解[J]. 《山东大学学报(理学版)》, 2023, 58(11): 127-134, 146.
[14] 王力工,郁志明,周枫,陶丽杰,邢露淇. 基于完全图构造的两类整图[J]. 《山东大学学报(理学版)》, 2023, 58(11): 155-159.
[15] 王冉冉,文飞,张树成. 一类图的广义特征多项式[J]. 《山东大学学报(理学版)》, 2023, 58(11): 165-174.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 吴鹏飞,孟祥增,刘俊晓,马凤娟 . 基于结构与内容的网页主题信息提取研究[J]. J4, 2006, 41(3): 131 -134 .
[2] 马新光. Dirichlet空间到Bloch空间的一个积分型算子[J]. J4, 2012, 47(4): 66 -69 .
[3] 夏梦南, 杜永萍, 左本欣. 基于依存分析与特征组合的微博情感分析[J]. 山东大学学报（理学版）, 2014, 49(11): 22 -30 .
[4] 严为绒, 洪宇, 朱珊珊, 车婷婷, 姚建民, 朱巧明. 基于语义场景的隐式篇章关系检测方法[J]. 山东大学学报（理学版）, 2014, 49(11): 59 -67 .
[5] 朱梦珺,蒋洪迅,许伟. 基于金融微博情感与传播效果的股票价格预测[J]. 山东大学学报（理学版）, 2016, 51(11): 13 -25 .
[6] . 基于移相法的三维面型测量系统优化算法研究[J]. J4, 2009, 44(6): 40 -45 .
[7] 胡丽霞,张建华. 三角代数上的零点Lie高阶可导映射[J]. J4, 2013, 48(4): 5 -9 .
[8] 李影, 宋卫东. 关于deSitter空间中的伪脐类时子流形[J]. 山东大学学报（理学版）, 2015, 50(10): 64 -67 .
[9] 吴洪博,乔希民, . 命题逻辑系统Ｌn中公式相对于有限理论的∑Γ－模糊真度理论[J]. J4, 2008, 43(6): 1 -8 .
[10] 隋云云. 五值非线性序集逻辑系统中命题真度的分布[J]. J4, 2009, 44(1): 78 -82 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发