Distinguishing Polynomials of Graphs

For a graph G, a k-coloring c: V (G) \1, 2, , k\ is called distinguishing, if the only automorphism f of G with the property c (v) =c (f (v) ) for every vertex v G (color-preserving automorphism), is the identity. In this paper, we show that the number of distinguishing k-colorings of G is a monic polynomial in k, calling it the distinguishing polynomial of G. Furthermore, we compute the distinguishing polynomials of cycles and complete multipartite graphs. We also show that the multiplicity of zero as a root of the distinguishing polynomial of G is at least the number of orbits of G.