Distinguishing and Distinguishing Chromatic Numbers of Generalized Petersen Graphs
John Weigand, Michael S. Jacobson · 2008
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.