The distinguishing number of the hypercube

被引：53

作者：

Bogstad, B ^{[1
]}

Cowen, LJ ^{[1
]}

机构：

[1] Tufts Univ, Dept Comp Sci, Medford, MA 02155 USA

来源：

DISCRETE MATHEMATICS | 2004年 / 283卷 / 1-3期

关键词：

symmetry breaking; distinguishing number; automorphism groups; hypercube; graph coloring;

D O I：

10.1016/j.disc.2003.11.018

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. It is shown, for the d-dimensional hypercubic graphs H-d, that D(H-d) = 3 if d is an element of {2,3} and D(H-d) = 2 if d greater than or equal to 4. It is also shown that D(H-d(2)) = 4 for d is an element of {2, 3} and D(H-d(2)) = 2 for d greater than or equal to 4, where H-d(2) denotes the square of the d-dimensional hypercube. This solves the distinguishing number for hypercubic graphs and their squares. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：29 / 35

页数：7