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

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (6): 44-55.doi: 10.6040/j.issn.1671-9352.0.2022.649

•   • 上一篇    下一篇

单圈图的邻点可约全标号

王丽(),李敬文*(),杨文珠,裴华艳   

  1. 兰州交通大学电子与信息工程学院，甘肃 兰州 730070
  • 收稿日期:2022-12-27 出版日期:2024-06-20 发布日期:2024-06-17
  • 通讯作者: 李敬文 E-mail:1175133725@qq.com;lijingwen28@163.com
  • 作者简介:王丽(1999—)，女，硕士研究生，研究方向为图论算法及其应用. E-mail: 1175133725@qq.com
  • 基金资助:
    国家自然科学基金资助项目(11961041);国家自然科学基金资助项目(62262038);甘肃省媒体融合技术与传播重点实验室资助项目(21ZD8RA008)

Adjacent vertex reducible total labeling of unicyclic graphs

Li WANG(),Jingwen LI*(),Wenzhu YANG,Huayan PEI   

  1. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
  • Received:2022-12-27 Online:2024-06-20 Published:2024-06-17
  • Contact: Jingwen LI E-mail:1175133725@qq.com;lijingwen28@163.com

RichHTML

1

PDF (PC)

164

摘要：

针对单圈型运输网络在特殊情景下的标号问题，借鉴智能算法思路，设计一种新的启发式搜索算法，可判别有限点内所有单圈图是否存在邻点可约全标号。通过对单圈图图集进行实验分析，找到几类单圈图的标号特性，得到若干定理，并给出猜想：所有的单圈图均为AVRTL图。

关键词: 单圈图, 邻点可约全标号, 标号算法, 联图

Abstract:

A new heuristic search algorithm is designed for the labeling problem of unicyclic transport networks in special scenarios, drawing on the ideas of intelligent algorithms, which can discriminate whether there is an adjacent vertex reducible total labeling for all unicyclic graphs within a finite number of vertices. Through experimental analysis of the set of unicyclic graphs, the labeling properties of several types of unicyclic graphs are found, several theorems are obtained, and a conjecture is given: All unicyclic graphs are AVRTL graphs.

Key words: unicyclic graph, adjacent vertex reducible total labeling, labeling algorithm, joint graph

中图分类号: 

  • O157.5

图1

S4↑C8和S5↓C6"

图2

SUN7, 2和(8, 5)-K"

图3

邻点可约全标号示例"

图4

Cn "

图5

Cn的标号结果图"

图6

(n, t)-K"

图7

SUNn, m"

图8

Sm↑Cn"

图9

(n, t)-K↑Pm"

图10

Sn↓Cm"

1 ROSAA.On certain valuations of the vertices of a graph[J].Theory of Graphs,1967,1967,349-355.
2 KOTZIGA,ROSAA.Magic valuations of finite graphs[J].Canadian Mathematical Bulletin,1970,13(4):451-461.
doi: 10.4153/CMB-1970-084-1
3 MACDOUGALLJ A,MILLERM,WALLISW D.Vertex-magic total labeling of graphs[J].Utilitas Mathematics,2002,61,3-21.
4 BURRIS A C. Vertex-distinguishing edge-colorings[D]. Memphis: Memphis State University, 1993: 1-9.
5 BALISTERP N,RIORDANO M,SCHELPR H.Vertex-distinguishing edge coloring of graphs[J].Graph Theory,2003,42(2):95-109.
doi: 10.1002/jgt.10076
6 ZHANGZhongfu,LIULinzhong,WANGJianfang.Adjacent strong edge coloring of graphs[J].Applied Mathematics Letters,2002,15(5):623-626.
doi: 10.1016/S0893-9659(02)80015-5
7 ZHANGZhongfu,CHENXiang'en,LIJingwen,et al.On adjacent vertex distinguishing total coloring of graphs[J].Science in China Series A: Mathematics,2005,48(3):289-299.
doi: 10.1360/03YS0207
8 ZHANGZhongfu,LIJingwen.D(β)-vertex distinguishing edge coloring of graphs[J].Journal of Mathematics,2006,49(3):703-708.
9 ZHANGZhongfu,LIJingwen,CHENXiang'en,et al.D(β)-vertex distinguishing total coloring of graphs[J].Science in China Series A: Mathematics,2006,49(10):1430-1440.
doi: 10.1007/s11425-006-2029-x
10 ZHANGZhongfu,QIUPengxiang,XUBaogen,et al.Vertex distinguishing total coloring of graphs[J].ARS Combinatoria,2008,87(2):33-45.
11 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 Press, 2009: 1-3.
12 张园萍,强会英,孙亮萍.星扇轮联图的邻点可约边染色[J].数学的实践与认识,2012,42(13):207-213.
doi: 10.3969/j.issn.1000-0984.2012.13.030
ZHANGYuanping,QIANGHuiying,SUNLiangping.Adjacent reducible edge coloring of star fan wheel of joint-graphs[J].Mathematics in Practice and Theory,2012,42(13):207-213.
doi: 10.3969/j.issn.1000-0984.2012.13.030
13 王笔美,李敬文,顾彦波,等.单圈图的边幻和全标号[J].山东大学学报(理学版),2020,55(9):42-50.
WANGBimei,LIJingwen,GUYanbo,et al.Edge-magic total labeling of unicyclic graphs[J].Journal of Shandong University (Natural Science),2020,55(9):42-50.
14 罗榕,李敬文,张树成,等.若干联图的邻点和可约边染色[J].华中师范大学学报(自然科学版),2023,57(2):201-207.
LUORong,LIJingwen,ZHANGShucheng,et al.Adjacent points sum reducible edge coloring of some joint graphs[J].Journal of Central China Normal University (Natural Sciences),2023,57(2):201-207.
[1] 朱利娜,李敬文,孙帅. 几类联图的L(2, 1)-边染色算法研究[J]. 《山东大学学报(理学版)》, 2023, 58(8): 63-72.
[2] 兰琳钰,李敬文,张树成,张丽景,申化玉. 图的点可约全标号算法研究[J]. 《山东大学学报(理学版)》, 2023, 58(11): 135-146.
[3] 谭钧铭,强会英,王洪申. 单圈图的邻和可区别边染色[J]. 《山东大学学报(理学版)》, 2022, 57(2): 78-83.
[4] 王笔美,李敬文,顾彦波,邵淑宏. 单圈图的边幻和全标号[J]. 《山东大学学报(理学版)》, 2020, 55(9): 42-50.
[5] 谢建民,姚兵,赵廷刚. 广义太阳图Sm,n奇优雅标号算法及实现[J]. 山东大学学报（理学版）, 2016, 51(4): 79-85.
[6] 张芳红1, 王治文2, 陈祥恩1*，姚兵1. K5∨Kt邻点可区别全色数[J]. J4, 2012, 47(12): 37-40.
[7] 蔡华, 苗杰. n阶单圈图的边平均Wiener指标[J]. J4, 2012, 47(10): 70-74.
[8] 王倩,田双亮. 若干联图的邻点可区别关联染色[J]. J4, 2011, 46(8): 89-91.
[9] 田双亮. 等广义联图的 Mycielski 图的星全染色[J]. J4, 2010, 45(6): 23-26.
[10] 李敬文,徐保根,李沐春,张忠辅,赵传成,任志国 . Pm∨Cn的点可区别边色数[J]. J4, 2008, 43(8): 24-27 .
[11] 冯新磊,赵建立, . 极大加广义正定矩阵[J]. J4, 2007, 42(8): 70-73 .
[12] 秦 健,张 岩 . 单圈图和双圈图的动态色数[J]. J4, 2007, 42(10): 37-40 .
[13] 刘晓妍,李乐学 . 拟阵基关联图中的路[J]. J4, 2006, 41(2): 52-53 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 刘保仓,史开泉 . S-粗集的信度特征[J]. J4, 2006, 41(5): 26 -29 .
[2] 郭 会,林 超 . 对流占优Sobolev方程的最小二乘特征混合有限元方法[J]. J4, 2008, 43(9): 45 -50 .
[3] 唐风琴1,白建明2. 一类带有广义负上限相依索赔额的风险过程大偏差[J]. J4, 2013, 48(1): 100 -106 .
[4] 王　瑶,刘　建,王仁卿,* . 阿利效应及其对生物入侵和自然保护中小种群管理的启示[J]. J4, 2007, 42(1): 76 -82 .
[5] . 极限limλ→0 Y(λI+AY) -1存在的充要条件[J]. J4, 2009, 44(6): 10 -13 .
[6] 李新华,董守平,赵志勇,陈俊峰, . 减阻沟槽表面近壁湍流相干运动的实验研究[J]. J4, 2006, 41(2): 106 -110 .
[7] 李兆丽,丰 晓* . 特征列、Grbner基和良性基方法的实施、比较和改进[J]. J4, 2008, 43(4): 89 -96 .
[8] 李俊奎,王元珍,李 专 . Azszp: 一种基于规则的数据清洗方案[J]. J4, 2007, 42(9): 71 -74 .
[9] 张丽,许玉铭 . σ1-空间及其性质[J]. J4, 2006, 41(5): 30 -32 .
[10] 刘才然, 宋贤梅. 环Fl+vFl+v2Fl上的二次剩余码[J]. 山东大学学报（理学版）, 2014, 49(10): 45 -49 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发