The number of distinguishing colorings of a Cartesian product graph

DOI10.2989/16073606.2023.2274580MaRDI QIDQ6504592arXivFDO

Authors Saeid Alikhani, Mohammad Hadi Shekarriz

Published in arXiv

Full work available at URL https://doi.org/10.2989/16073606.2023.2274580

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A vertex coloring is called distinguishing if the identity is the only automorphism that can preserve it. The distinguishing number of a graph is the minimum number of colors required for such a coloring. The distinguishing threshold of a graph $G$ is the minimum number of colors $k$ required that any arbitrary $k$-coloring of $G$ is distinguishing. We prove a statement that gives a necessary and sufficient condition for a vertex coloring of the Cartesian product to be distinguishing. Then we use it to calculate the distinguishing threshold of a Cartesian product graph. Moreover, we calculate the number of non-equivalent distinguishing colorings of grids.

This page was built for publication: The number of distinguishing colorings of a Cartesian product graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6504592)