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

《山东大学学报(理学版)》 ›› 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)

276

摘要： 对于图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]. 《山东大学学报(理学版)》, 2020, 55(6): 10-16.
[2] 贾汉,韩益亮,吴旭光. 基于时序和TOPSIS的社交网络节点重要性评价算法[J]. 《山东大学学报(理学版)》, 2020, 55(5): 88-94.
[3] 徐江珮,王晋,刘畅,周亮,龙凤. 电动汽车充电桩CAN总线协议的安全检测[J]. 《山东大学学报(理学版)》, 2020, 55(5): 95-104.
[4] 唐益明,张征,芦启明. 分段二次方转换函数驱动的高斯核模糊C均值聚类[J]. 《山东大学学报(理学版)》, 2020, 55(3): 107-112.
[5] 刘洋,赵科军,葛连升,刘恒. 一种基于深度学习的快速DGA域名分类算法[J]. 《山东大学学报(理学版)》, 2019, 54(7): 106-112.
[6] 王文卿,撖奥洋,于立涛,张智晟. 自编码器与PSOA-CNN结合的短期负荷预测模型[J]. 《山东大学学报(理学版)》, 2019, 54(7): 50-56.
[7] 卢政宇,李光松,申莹珠,张彬. 基于连续特征的未知协议消息聚类算法[J]. 《山东大学学报(理学版)》, 2019, 54(5): 37-43.
[8] 徐炜娜,张广乐,李仕红,陈园园,李强,杨涛,许明敏,乔宁,张良云. 基于随机森林算法识别基因间长非编码RNA[J]. 《山东大学学报(理学版)》, 2019, 54(3): 85-92, 101.
[9] 刘双根,王蓉蓉,李圣雨. GF(3m)上Hessian曲线的三进制Montgomery算法[J]. 《山东大学学报(理学版)》, 2019, 54(1): 96-102.
[10] 许力冬,王明强. 对10轮AES-128的中间相遇攻击[J]. 山东大学学报（理学版）, 2018, 53(7): 39-45.
[11] 崔朝阳,孙甲琦,徐松艳,蒋鑫. 适用于集群无人机的自组网安全分簇算法[J]. 山东大学学报（理学版）, 2018, 53(7): 51-59.
[12] 何新华,万帆,胡文发,郑爱兵. 复杂风险变量随机模拟下的应急供应调度[J]. 山东大学学报（理学版）, 2018, 53(5): 1-11.
[13] 宋省身,杨岳湘,江宇. 基于单指令级并行的快速求交算法[J]. 山东大学学报（理学版）, 2018, 53(3): 54-62.
[14] 刘园园,曹德欣,秦军. 非线性二层混合整数规划问题的区间算法[J]. 山东大学学报（理学版）, 2018, 53(2): 9-17.
[15] 李国成,王继霞. 交叉熵蝙蝠算法求解期权定价模型参数估计问题[J]. 《山东大学学报(理学版)》, 2018, 53(12): 80-89.
Viewed
Full text


Abstract

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