Breaking the Symmetries of the Book Graph and the Generalized Petersen Graph
Arbind Kumar Lal, Bikash Bhattacharjya · SIAM Journal on Discrete Mathematics · 2009
An r-labeling of the vertices of a graph $G=(V(G),E(G))$, $f:V(G)\longrightarrow\{1,2,\ldots,r\}$, is said to be distinguishing provided that no nontrivial automorphism of G preserves all of the vertex labels. The distinguishing number of G, denoted by $D(G)$, 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}$.