华东师范大学学报(自然科学版)

• 数学 • 上一篇    下一篇

一种证明(k, d)-强优美树的新方法

赵喜杨, 王晓敏, 姚兵   

  1. 西北师范大学 数学与统计学院, 兰州 730070
  • 收稿日期:2015-06-24 出版日期:2016-07-25 发布日期:2016-09-29
  • 通讯作者: 姚兵, 男, 教授, 研究方向为图着色与标号以及复杂网络. E-mail: yybb918@163.com
  • 基金资助:

    国家自然科学基金(61163054, 61163037, 61363060)

A new method for proving strongly (k, d)-graceful trees

ZHAO Xi-yang, WANG Xiao-min, YAO Bing   

  1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China
  • Received:2015-06-24 Online:2016-07-25 Published:2016-09-29

摘要:

在现有研究的很多图优美问题中, 发现了一种叫做悬挂和拆分的新方法. 利用此新方法可以构造出较大规模的具有~$(k,d)$-强优美标号, 并证明了新方法所构造出的(k,d)-强优美树的正确性, 且由 (k,d)-强优美标号可导出强奇优美标号. 此新方法较易转化为优良的算法, 为(k,d)-强优美标号应用于网络提供了可行的理论保证.

关键词: (k,d)-强优美标号; 强奇优美标号, 完美匹配

Abstract:

In investigating graph graceful problem that has many applications in the real world, we discovery a new method called the appending-split method. By this new
method we can construct large scale of trees having strongly (k, d)-graceful labellings, and provide the proof for the correctness of constructed (k, d)-graceful trees. Furthermore, such strongly (k, d)-graceful labellings can induce strongly odd-graceful labellings. Our new method can be easily transformed into a good algorithm that may be a theoretical guarantee for applying strongly (k, d)-graceful labellings to network.

Key words: strongly (k, d)-graceful labelling, strongly odd-graceful labelling, perfect matching