The distinguishing number of Cartesian products of complete graphs

DOI10.1016/j.ejc.2007.11.018zbMath1205.05198OpenAlexW2081088856MaRDI QIDQ2427541

Wilfried Imrich, Janja Jerebic, Sandi Klavžar

Publication date: 13 May 2008

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2007.11.018

zbMATH Keywords

Cartesian productvertex labelingdistinguishing numberswitching lemma

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph operations (line graphs, products, etc.) (05C76)

Related Items (27)

An upper bound on the distinguishing index of graphs with minimum degree at least two ⋮ Extending precolorings to distinguish group actions ⋮ Distinguishing graphs with intermediate growth ⋮ Distinguishing number and distinguishing index of strong product of two graphs ⋮ Distinguishing number of hierarchical products of graphs ⋮ Trees with distinguishing number two ⋮ Nordhaus-Gaddum theorem for the distinguishing chromatic number ⋮ Distinguishing threshold of graphs ⋮ Endomorphism breaking in graphs ⋮ List-distinguishing Cartesian products of cliques ⋮ Distinguishing numbers and distinguishing indices of oriented graphs ⋮ A bound for the distinguishing index of regular graphs ⋮ Improving upper bounds for the distinguishing index ⋮ Distinguishing graphs by edge-colourings ⋮ Distinguishing Cartesian products of countable graphs ⋮ The list distinguishing number equals the distinguishing number for interval graphs ⋮ The chromatic distinguishing index of certain graphs ⋮ Infinite motion and 2-distinguishability of graphs and groups ⋮ Distinguishing colorings of Cartesian products of complete graphs ⋮ The distinguishing chromatic number of Cartesian products of two complete graphs ⋮ On the distinguishing number of cyclic tournaments: towards the Albertson-Collins conjecture ⋮ Distinguishing chromatic numbers of complements of Cartesian products of complete graphs ⋮ Distinguishing index of Kronecker product of two graphs ⋮ The determining number of a Cartesian product ⋮ Nordhaus-Gaddum type inequalities for the distinguishing index ⋮ Number of distinguishing colorings and partitions ⋮ Precise bounds for the distinguishing index of the Cartesian product

Cites Work

• Unnamed Item
• On computing the distinguishing numbers of trees and forests
• The distinguishing chromatic number
• Cartesian powers of graphs can be distinguished by two labels
• On the local distinguishing numbers of cycles
• A note on the asymptotic and computational complexity of graph distinguishability
• The distinguishing number of the hypercube
• Distinguishing numbers for graphs and groups
• Symmetry breaking in graphs
• Distinguishing colorings of Cartesian products of complete graphs
• The maximum distinguishing number of a group
• The distinguishing number of the direct product and wreath product action.
• Distinguishing labellings of group action on vector spaces and graphs
• Distinguishing Cartesian powers of graphs
• Distinguishing Cartesian powers of graphs

This page was built for publication: The distinguishing number of Cartesian products of complete graphs