DISTINGUISHING AND DISTINGUISHING CHROMATIC NUMBERS OF GENERALIZED PETERSEN GRAPHS

被引：0

作者：

Weigand, John ^{[1
]}

Jacobson, Michael ^{[1
]}

机构：

[1] Univ Colorado Denver, Dept Math & Stat Sci, Denver, CO 80217 USA

来源：

AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS | 2008年 / 5卷 / 02期

关键词：

graph; graph automorphism; vertex coloring; distinguishing number;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Albertson and Collins defined the distinguishing number of a graph to be the smallest number of colors needed to color its vertices so that the coloring is preserved only by the identity automorphism. Collins and Trenk followed by defining the distinguishing chromatic number of a graph to be the smallest size of a coloring that is both proper and distinguishing. We show that, with two exceptions, generalized Petersen graphs are 2-distinguishable and properly 3-distinguishable.

引用

页码：199 / 211

页数：13

共 9 条

[1]

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

[2]

Albertson MO, 2007, ELECTRON J COMB, V14

[3]

Albertson MO, 2005, ELECTRON J COMB, V12

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

Bogstad, B ;

Cowen, LJ .

DISCRETE MATHEMATICS, 2004, 283 (1-3) :29-35

[5]

Collins KL, 2006, ELECTRON J COMB, V13

[6] GROUPS OF GENERALIZED PETERSEN GRAPHS [J].

FRUCHT, R ;

GRAVER, JE ;

WATKINS, ME .

PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY-MATHEMATICAL AND PHYSICAL SCIENCES, 1971, 70 (SEP) :211-&

[7]

Harary F., 2001, DISCUSS MATH GRAPH T, V21, P149

[8] Distinguishing Cartesian powers of graphs [J].

Imrich, Wilfried ;

Klavzar, Sandi .

JOURNAL OF GRAPH THEORY, 2006, 53 (03) :250-260

[9] Cartesian powers of graphs can be distinguished by two labels [J].

Klavzar, Sandi ;

Zhu, Xuding .

EUROPEAN JOURNAL OF COMBINATORICS, 2007, 28 (01) :303-310

← 1 →