Distinguishing threshold for some graph operations

Abstract

A vertex coloring of a graph $G$ is distinguishing if non-identity automorphisms do not preserve it. The distinguishing number, $D(G)$, is the minimum number of colors required for such a coloring and the distinguishing threshold, $\theta (G)$, is the minimum number of colors~$k$ such that any arbitrary $k$-coloring is distinguishing. Moreover, ${\Phi }_k(G)$ is the number of distinguishing coloring of $G$ using at most $k$ colors. In this paper, for some graph operations, namely, vertex-sum, rooted product, corona product and lexicographic product, we find formulae of the distinguishing number and threshold using ${\Phi }_k(G)$.

20 pages, 5 figures

References in corpus (2)

• Number of Distinguishing Colorings and Partitions
• Distinguishing threshold of graphs

Cited by in corpus (2)

• Number of colors needed to break symmetries of a graph by an arbitrary edge coloring
• The number of distinguishing colorings of a Cartesian product graph