Small Label Classes in 2-Distinguishing Labelings

被引:12
作者
Boutin, Debra L. [1 ]
机构
[1] Hamilton Coll, Clinton, NY 13323 USA
关键词
Graph; distinguishing labeling; automorphism group;
D O I
10.26493/1855-3974.31.d93
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A graph G is said to be 2-distinguishable if there is a labeling of the vertices with two labels so that only the trivial automorphism preserves the labels. Call the minimum size of a label class in such a labeling of G the cost of 2-distinguishing G and denote it by rho(G). This paper shows that for n >= 5, [log(2) n] + 1 <= rho(Q(n)) <= 2[log(2) n] - 1, where Q(n) is the hypercube of dimension n.
引用
收藏
页码:154 / 164
页数:11
相关论文
共 9 条
[1]  
Albertson M. O., 1996, ELECTRON J COMB, V3, DOI DOI 10.37236/1242
[2]  
Albertson MO, 2007, ELECTRON J COMB, V14
[3]   The distinguishing number of the hypercube [J].
Bogstad, B ;
Cowen, LJ .
DISCRETE MATHEMATICS, 2004, 283 (1-3) :29-35
[4]  
Boutin DL, 2006, ELECTRON J COMB, V13
[5]  
BOUTIN DL, J GRAPH THE IN PRESS
[6]  
FUKUDA T, 2006, 3 CONNECTED PLANAR G
[7]  
IMRICH W, COMMUNICATION
[8]  
IMRICH W, 2000, WIL INT S D, pR13
[9]   Distinguishing Cartesian powers of graphs [J].
Imrich, Wilfried ;
Klavzar, Sandi .
JOURNAL OF GRAPH THEORY, 2006, 53 (03) :250-260