华东师范大学学报（自然科学版） >

2016 , Vol. 2016 >Issue 4: 70 - 76

DOI: https://doi.org/10.3969/j.issn.1000-5641.2016.04.008

数学

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

  • 赵喜杨 ,
  • 王晓敏 ,
  • 姚兵
展开
  • 西北师范大学 数学与统计学院, 兰州 730070

收稿日期: 2015-06-24

  网络出版日期: 2016-09-29

基金资助

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

收起

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

  • ZHAO Xi-yang ,
  • WANG Xiao-min ,
  • YAO Bing
Expand
  • College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China

Received date: 2015-06-24

  Online published: 2016-09-29

Fold

摘要

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

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

本文引用格式

赵喜杨 , 王晓敏 , 姚兵 . 一种证明(k, d)-强优美树的新方法[J]. 华东师范大学学报（自然科学版）, 2016 , 2016(4) : 70 -76 . DOI: 10.3969/j.issn.1000-5641.2016.04.008

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

参考文献

[ 1 ] GNANAJOTHI R B. Topics in graph theory[D]. Madurai: Madurai Lamaraj University, 1991.
[ 2 ] WEI L X, ZHANG K L. The graceful graphs on several kinds of union graphs[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2008, 47(3): 10-13.
[ 3 ] WANG T, LIU H S, LI D M. Gracefulness of the graphs related to wheel[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni 2011, 50(6): 16-19.
[ 4 ] YAO B, YANG C, YAO M, et al. Graphs as models of scale-free networks[J]. Applied Mechanics and Materials, 2013, 380/381/382/383/384: 2034-2037.
[ 5 ] YANG S H, YAO B, YAO M, et al. Labeling sun-like graphs from scale-free small-world network models[ C]//Proceedings of the 6th International Conference on Measuring Technology and Mechatronics Automation. IEEE, 2014: 378-384.
[ 6 ] GALLIAN J A. A dynamic survey of graph labeling[J/OL]. The Electronic Journal of Combinatorics,2011[ 2015-04-01].http://www. emis. ains. org/journals/EJC/surveys/ds6. pdf.
[ 7 ] ZHOU X Q, YAO B, CHEN X E. Every lobster is odd-elegant[J]. Information Processing Letters, 2013,113(1/2):30-33.
[ 8 ] ZHOU X Q, YAO B, CHEN X E, et al. A proof to the odd-gracefulness of all lobsters[J]. Ars Combinatoria, 2012, 103: 13-18.
[ 9 ] ROSA A. On certain valuation of the vertices of a graph[M]//Theory of Graphs, New York: Gordon and Breach, 1967:349-355.
[10] BONDY A J, MURTY U S R. Graph Theory with Applications[M]. London :The MaCmillan Press Ltd, 1976.
[11] 郭璟霞，姚兵，张家娟.关于边对称树的广义优美性[J].西南大学学报（自然科学版），2013, 35(2):62-68.

Options
文章导航

/

〈 〉