The number of distinguishing colorings of a Cartesian product graph (Q6558479)

A vertex colouring of a graph is distinguishing if the identity is the only automorphism that preserves it. The distinguishing threshold \(\theta(G)\) of a graph \(G\) is then the minimum number \(t\) of colours ensuring that any arbitrary \(k\)-colouring of \(G\) with \(k\ge t\) is distinguishing. The paper calculates the distinguishing threshold of a Cartesian product graph.\N\NA graph \(G\) is prime if it cannot be represented as the Cartesian product of two graphs nonisomorphic with \(G\). Every graph has a unique prime factorisation with respect to the Cartesian product. Additionally, the \(i\)th quotient subgraph \(Q_{i}\) of a Cartesian product \(G = G_{1}\Box G_{2}\Box\cdots \Box G_{k}\) is defined as\N\[\NQ_{i}=G/G_{i}=G_{1}\Box \cdots G_{i-1}\Box G_{i+1}\cdots \Box G_{k}.\N\]\NIt follows that \(G=G_{i}\Box Q_{i}\). The main results of the paper are the following:\N\NTheorem. Let \(k\ge2\) and let \(G = G_{1}\Box G_{2}\Box\cdots \Box G_{k}\) be a prime factorisation with pairwise non-isomorphic connected factors. Then\N\[\N\theta(G)=\max\{(\theta(G_{i})-1)\times |Q_{i}|:i=1,\ldots,k\}+1.\N\]\NFor \(k\ge 2\), the \(k\)-th Cartesian power of a graph \(G\) is \(G^{k} = G\Box G^{k-1}\).\N\NTheorem. Let \(k\ge2\) and let \(G\) be a connected prime graph. Then\N\[\N\theta(G^{k})=|G|^{k-1}\times \max\left\{\frac{|G|+1}{2}, \theta(G)-1\right\}+1.\N\]