Distinguishing Cartesian powers of graphs (Q5921670): Difference between revisions

Let \(G\) be a graph with a labeling \(c : V(G)\to\{1,2,\dots,d\}\). A labeling \(c\) of \(G\) is said to be \(d\)-distinguishing if only the identical automorphism of the graph \(G\) preserves the labeling \(c\). The distinguishing number \(D(G)\) of \(G\) is the minimum \(d\) such that \(G\) has a \(d\)-distinguishing labeling. The authors prove that \(D(G^r)\) holds for all \(r\geq 4\) if \(G\) is a prime graph with respect to the Cartesian product and \(\square\) denotes the Cartesian product of \(G\) (i.e. \(G^r = G\square\cdots \square G)\).