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

赵喜杨; 王晓敏; 姚兵

doi:10.3969/j.issn.1000-5641.2016.04.008

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

doi: 10.3969/j.issn.1000-5641.2016.04.008

1.
西北师范大学数学与统计学院, 兰州 730070

基金项目:

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

详细信息

通讯作者:
姚兵, 男, 教授, 研究方向为图着色与标号以及复杂网络. E-mail: yybb918@163.com

计量
- 文章访问数: 191
- HTML全文浏览量: 13
- PDF下载量: 388
- 被引次数: 0
出版历程
- 收稿日期: 2015-06-24
- 刊出日期: 2016-07-25

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

1.
College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China

摘要

摘要: 在现有研究的很多图优美问题中, 发现了一种叫做悬挂和拆分的新方法. 利用此新方法可以构造出较大规模的具有~$(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.
- strongly (k, d)-graceful labelling strongly odd-graceful labelling perfect matching /

HTML全文

参考文献(1)

[1]

[ 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.