The Gracefulness of A Kind of Chain Graph
Shiying Wang · Journal of Taiyuan University of Science and Technology · 2012
The study of the gracefulness of chain graph was undertaken.The chain graph was referred to graph T1、T2、T5,which is linked with k complete two partite graph K2,m1,K2,m2,…,K2,mk(of which k,n,m1,m2,…,mk are all the positive integer greater than 1).The study aimed at the gracefulness of chain graph T3 and T4,T3 is formed by the linkage of chain T1 and path Pn(of which the length is n),T4 is formed by the linkage of chain graph T2 and path Pn(of which the length is n).The graceful labeling was given to these kinds of graphs by construction method,and their graceness were proved.In the above study,the numerical value of m1,m2,…,mk can be expanded from 2 to the positive integer greater than 1,which can widen the road of the graceful graph and its application.At last,a supposition that some graphs respectively linked end to end with chain graph T1、T2、T3、T4、T5 could be graceful was put forward.