The distinguishing number of Cartesian products of complete graphs

被引：40

作者：

Imrich, Wilfried ^{[1
]}

Jerebic, Janja ^{[2
,3
]}

Klavzar, Sandi ^{[2
,3
]}

机构：

[1] Univ Leoben, A-8700 Leoben, Austria

[2] Univ Maribor, Dept Math & Comp Sci, SLO-2000 Maribor, Slovenia

[3] Inst Math Phys & Mech, Ljubljana 1000, Slovenia

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2008年 / 29卷 / 04期

关键词：

D O I：

10.1016/j.ejc.2007.11.018

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d labels that is preserved only by a trivial automorphism. We prove that Cartesian products of relatively prime graphs whose sizes do not differ too much can be distinguished with a small number of colors. We determine the distinguishing number of the Cartesian product K-k square K-n for all k and n, either explicitly or by a short recursion. We also introduce column-invariant sets of vectors and prove a switching lemma that plays a key role in the proofs. (c) 2007 Elsevier Ltd. All rights reserved.

引用

页码：922 / 929

页数：8

共 16 条

[1]

Albertson M.O., 1996, ELECT J COMBIN, V3

[2]

Albertson MO, 2005, ELECTRON J COMB, V12

[3] The distinguishing number of the hypercube [J].