The number of distinguishing colorings of a Cartesian product graph
type: Item
instance of: scholarly article
title: The number of distinguishing colorings of a Cartesian product graph
zbMATH Open document ID: 1547.05079
DOI: 10.2989/16073606.2023.2274580
author: Saeid Alikhani
author: Mohammad Hadi Shekarriz
published in: Quaestiones Mathematicae
publication date: 2024-06-19T00:00:00Z
review text: 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\]
reviewed by: Guillermo Pineda-Villavicencio
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C76
zbMATH DE Number: 7868217
MaRDI profile type: Publication
cites work: Number of distinguishing colorings and partitions
cites work: Symmetry breaking in graphs
cites work: Asymmetric trees with two prescribed degrees
cites work: The distinguishing number of the hypercube
cites work: Q3005852
cites work: The distinguishing number of Cartesian products of complete graphs
cites work: Distinguishing Cartesian powers of graphs
cites work: Distinguishing threshold of graphs
description: scientific article; zbMATH DE number 7868217