BREAKING THE SYMMETRIES OF THE BOOK GRAPH AND THE GENERALIZED PETERSEN GRAPH

作者：Lal A K^*; Bhattacharjya B

来源：SIAM Journal on Discrete Mathematics, 2009, 23(3): 1200-1216.

DOI：10.1137/080728640

• labeling
• automorphism group
• distinguishing number
• distinguishing chromatic number
• book graph
• generalized Petersen graph

An r-labeling of the vertices of a graph G = (V (G), E(G)), f : V (G) -> {1, 2, ... , r}, is said to be distinguishing provided that no nontrivial automorphism of G preserves all of the vertex labels. The distinguishing number of C, denoted by D(C), is the minimum r such that G has a distinguishing r-labeling. The distinguishing chromatic number chi(D)(G) of G is defined similarly, where, in addition, f is assumed to be a proper coloring. In this paper, we determine D(G) and chi(D)(G) of the book graph B(m,n), and chi(D)(G) of the generalized Petersen graph P(n,k).

• 出版日期2009