Number of distinguishing colorings and partitions.

A vertex coloring of a graph G is called distinguishing (or symmetry breaking) if no non-identity automorphism of G preserves it, and the distinguishing number, shown by D (G) , is the smallest number of colors required for such a coloring. This paper is about counting non-equivalent distinguishing colorings of graphs with k colors. A parameter, namely Φ k (G) , which is the number of non-equivalent distinguishing colorings of a graph G with at most k colors, is shown here to have an application in calculating the distinguishing number of the lexicographic product and the X -join of graphs. We study this index (and some other similar indices) which is generally difficult to calculate. Then, we show that if one knows the distinguishing threshold of a graph G , which is the smallest number of colors θ (G) so that, for k ≥ θ (G) , every k -coloring of G is distinguishing, then, in some special cases, counting the number of distinguishing colorings with k colors is very easy. We calculate θ (G) for some classes of graphs including the Kneser graph K (n , 2). We then turn to vertex partitioning by studying the distinguishing coloring partition of a graph G ; a partition of vertices of G which induces a distinguishing coloring for G. There, we introduce Ψ k (G) as the number of non-equivalent distinguishing coloring partitions with at most k cells, which is a generalization to its distinguishing coloring counterpart. [ABSTRACT FROM AUTHOR]