Breaking symmetries of some graph operations by vertex coloring
Mohammad Hadi Shekarriz, Seyed Alireza Talebpour Shirazi Fard, Bahman Ahmadi, Mohammad Hassan Shirdareh Haghighi, Saeid Alikhani · arXiv (Cornell University) · 2021
A vertex coloring of a graph $G$ is distinguishing if any non-identity automorphism of $G$ does not preserve it. The distinguishing number is the minimum number of colors required for such a coloring and the distinguishing threshold is the minimum number of colors~$k$ such that any arbitrary $k$-coloring is distinguishing. In this paper, we consider the distinguishing number and the distinguishing threshold for some graph operations, namely the vertex-sum of graphs as well as the rooted, corona and lexicographic product of graphs. As an important tool, we define a steady vertex of a graph as a vertex $v$ for which we have $\mathrm{Aut}(G-v)\cong\mathrm{stab}_{\mathrm{Aut}(G)}(v)$. Using this notion, we prove that a vertex $v$ is steady if and only if any distinguishing coloring for $G$ induces a distinguishing coloring for $G-v$.