Asymmetric colorings of products of graphs and digraphs (Q2026319)

The asymmetric coloring number (also called the distinguishing number) of a graph \(G\) is the least integer \(d\) such that there is a \(d\)-labeling of the vertices of \(G\) that is not preserved by any nontrivial automorphism of \(G\). The authors study the asymmetric coloring number of all main graph products: the strong, the direct, and the Cartesian product. Factors of the strong and the direct product considered in the paper are restricted to finite graphs and digraphs, while for the Cartesian product, previous results from [\textit{E. Estaji} et al., Discuss. Math., Graph Theory 37, No. 1, 155--164 (2017; Zbl 1354.05065)] are extended to finite or infinite digraphs with or without loops. It is shown that in most cases, the product of two graphs has an asymmetric 2-coloring. In order to obtain the results, the authors use the fact that all finite graphs have prime factorizations with respect to the strong and the direct product. Moreover, these factorizations are essentially. They also exploit the relationship between the automorphism group of a product of prime graphs with the groups of the factors.