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

《山东大学学报(理学版)》 ›› 2020, Vol. 55 ›› Issue (9): 42-50.doi: 10.6040/j.issn.1671-9352.0.2019.439

• • 上一篇    下一篇

单圈图的边幻和全标号

王笔美,李敬文*,顾彦波,邵淑宏   

  1. 兰州交通大学电子与信息工程学院, 甘肃 兰州 730070
  • 发布日期:2020-09-17
  • 作者简介:王笔美(1994— ),女,硕士研究生,研究方向为图论算法及其应用. E-mail:244315248@qq.com*通信作者简介:李敬文(1965— ),男,教授,研究方向为图论算法及其应用. E-mail:lijingwen28@163.com
  • 基金资助:
    国家自然科学基金资助项目(11961041;11461038)

Edge-magic total labeling of unicyclic graphs

WANG Bi-mei, LI Jing-wen*, GU Yan-bo, SHAO Shu-hong   

  1. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
  • Published:2020-09-17

PDF (PC)

672

摘要： 对于图G(p,q),若存在一个映射f:V(G)∪E(G)→{1,2,…,p+q},使得任意边uv∈E(G),满足f(u)+f(v)+f(uv)=K,K为常数,则图G(p,q)为边幻和图。设计了一种算法对16个点以内的单圈图进行标号,依据得到的结果,找到了两类特殊单圈图的标号规律,定义CnSymbolQC@〓Sm和CnΔSm来刻画此两类特殊单圈图,并给出其相关定理及证明。结果表明,点数小于等于16的所有单圈图均具有边幻和全标号,且其中绝大部分是超级边幻和全标号,从而猜测点数多于16的单圈图也具有边幻和全标号。

关键词: 边幻和全标号, 超级边幻和全标号, 单圈图, 算法

Abstract: An edge-magic total labeling is a one-to-one mapping f from V(G)∪E(G) onto {1,2,…,p+q} such that there exists a constant K satisfying f(u)+f(v)+f(uv)=K, for each uv∈E(G). A graph G(p,q) which has a edge-magic total labeling can be called edge-magic total labeling graph. An algorithm to label the unicyclic graphs with less than 16 vertices is designed. The rules of two special unicyclic graphs are obtained, and CnSymbolQC@Sm and CnΔSm to describe the two types of graphs are defiened, and related theorems are given and proved. The results show that all the unicyclic graphs with less than or equal to 16 vertices have a edge-magic total labeling, and most of them are super edge-magic total labeling. Therefore, it is speculated that the unicyclic graphs with more than 16 vertices also have the same characters.

Key words: edge-magic total labeling, super edge-magic total labeling, unicyclic graph, algorithm

中图分类号: 

  • O157.5
[1] GALLIAN J A. A dynamic survey of graph labeling[J]. The Electronic Journal of Combinatorics, 2009, 16(6):1-219.
[2] ROSA A. On certain valuations of the vertices of a graph[C]. Rome: Theory of Graphs, 1967: 349-355.
[3] GRAHAM R L, SLOANE N J A. On additive bases and harmonious graphs[J]. SIAM Journal on Algebraic Discrete Methods, 1980, 1(4):382-404.
[4] KOTZIG A, ROSA A. Magic valuations of finite graphs[J]. Canadian Mathematical Bulletin, 1970, 13(4):451-461.
[5] YEGNANARAYANAN V. On magic graphs[J]. Utilitas Mathematica, 2001, 59:181-204.
[6] LIN Y, MILLER M, SIMANJUNTAK R. Edge-magic total labelings of wheels, fans and friendship graphs[J]. Bulletin of the ICA, 2002, 35:89-98.
[7] FIGUEROA-CENTENO R M, ICHISHIMA R, MUNTANER-BATLE F A. The place of super edge-magic labelings among other classes of labelings[J]. Discrete Mathematics, 2001, 231(1/2/3):153-168.
[8] FIGUEROA-CENTENO R M, ICHISHIMA R, MUNTANER-BATLE F A. On the super edge-magic deficiency of graphs[J]. Electronic Notes in Discrete Mathematics, 2002, 11:299-314.
[9] ENOMOTO H, LLADO A S, NAKAMIGAWA T, et al. Super edge-magic graphs[J]. SUT Journal of Mathematics, 1998, 34(2):105-109.
[10] KOTZIG A, ROSA A. Magic valuations of complete graphs[J]. Centre de Recherches Mathematiques, Universite de Montreal, 1972, 17.
[11] LEE S M, KONG M C. On super edge-magic n-stars[J]. Journal of Combinatorial Mathematics and Combinatorial Computing, 2002, 42:87-96.
[12] MCKAY B D. Practical graph isomorphism[M]. Tennessee: Department of Computer Science, Vanderbilt University, 1981, 45-47.
[13] NGURAH A A G, SIMANJUNTAK R, BASKORO E T. On(super)edge-magic total labeling of subdivision of K1,3[J]. SUT Journal of Mathematics, 2007, 43(2):127-136.
[1] 张晓媛, 田毅, 任子涵, 段天宇, 杨斯媛, 张月轩. 拓扑邻域基在密度聚类算法中的应用[J]. 《山东大学学报(理学版)》, 2026, 61(5): 55-64.
[2] 孙歆怡,郑婷婷,孙丽雯. RIME-Transformer模型在复杂时序预测问题中的应用[J]. 《山东大学学报(理学版)》, 2026, 61(5): 79-89.
[3] 白月蓉,魏宗田,王德莉. 基于多火源燃烧连通度的网络抗毁性分析[J]. 《山东大学学报(理学版)》, 2026, 61(4): 102-108.
[4] 孙清,叶军,曾广财,宋苏洋,汪一心. 结合蝙蝠算法和紧密度改进的三支K-means算法[J]. 《山东大学学报(理学版)》, 2026, 61(1): 65-75.
[5] 杨玉,孙圣博,徐子瑞,蒋效伟,宋强,戴红伟. 基于混合变异灰狼优化算法的泊位-岸桥调度[J]. 《山东大学学报(理学版)》, 2026, 61(1): 94-102.
[6] 严莉,呼海林,王高洲,张闻彬,潘法定,张啸,郑艳伟. 基于长短时序预测的拓扑构建与控制[J]. 《山东大学学报(理学版)》, 2025, 60(9): 41-51.
[7] 刘福国,刘圆梦,石玉峰,田茂再. 基于VMD-DBO-BiGRU的多因素铁矿石期货价格预测[J]. 《山东大学学报(理学版)》, 2025, 60(9): 121-132.
[8] 刘魏岩,齐迹,梁红,林钰川. 基于混合策略的鹈鹕优化算法[J]. 《山东大学学报(理学版)》, 2025, 60(9): 52-61.
[9] 王江,李敬文,高鑫,孙亮晶. 若干联图的邻点可约全标号[J]. 《山东大学学报(理学版)》, 2025, 60(8): 57-67.
[10] 董海,张晨. 基于可持续和个性化的新能源汽车零件供应链网络设计[J]. 《山东大学学报(理学版)》, 2025, 60(6): 45-62.
[11] 孙岩,张正,张夏然,刘耘麟,孙国华. 多重不确定环境下带有模糊软时间窗的多式联运路径优化与仿真[J]. 《山东大学学报(理学版)》, 2025, 60(6): 128-140.
[12] 闫晟煜,刘杨,刘继祥,陈海峰,郑元旺,温福华,王洪瑀. 基于GA-BP神经网络模型的二手载货汽车价值评估方法[J]. 《山东大学学报(理学版)》, 2025, 60(12): 11-20.
[13] 梁霞,郭洁. 基于在线评论的线上教学平台选择方法[J]. 《山东大学学报(理学版)》, 2024, 59(9): 108-118.
[14] 邵伟,朱高宇,于雷,郭嘉丰. 高维数据的降维与检索算法[J]. 《山东大学学报(理学版)》, 2024, 59(7): 27-43.
[15] 王丽,李敬文,杨文珠,裴华艳. 单圈图的邻点可约全标号[J]. 《山东大学学报(理学版)》, 2024, 59(6): 44-55.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发