THE DISTINGUISHING NUMBER OF HALIN GRAPHS

摘要：

The distinguishing number of a graph G is the minimum number of colors for which there exists an assignment of colors to the vertices of G so that the group of color-preserving automorphisms of G consists only of the identity, denoted by D(G). According to the hamilton property of halin graphs, it is shown that the distinguishing number of 3-regular Halin graph G is 3 and 2, respectively, on 4 and above 6 vertices. And then combining with the distinguishing labeling of the cycle Cn with n vertices, it is also shown, for the n-vertex Halin graph with △(G)= m(≥4), that D(G)=3 if m=4 and n=5 or m=5 and n=6, otherwise D(G)=2, where △(G) denotes the maximum degree of G. This solves the distinguishing number for halin graphs.

关键词： Graph theory Distinguishing number Halin Graphs Graph coloring Automorphism group

作者: ZHIJUN GAO YI LI CHENGZHI JIANG MINGFENG YE

作者单位: College of Computer and Information Engineering of Heiloagjiang of Science and Technology, Harbin, 150027, China

会议类型: 国际会议

会议名称: The Second International Conference on Information & Systems Sciences(ICISS2008)(第二届信息与系统科学国际会议)

会议地点: 大连

会议语种:英文

页码: 1066-1073

在线出版日期: 2008-12-18（万方平台首次上网日期，不代表论文的发表时间）