The distinguishing number of the augmented cube and hypercube powers

DOI10.1016/J.DISC.2006.09.056MaRDI QIDQ2483424zbMATH OpenOpenAlexFDO

Authors Melody Chan

Publication date 28 April 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0601361

zbMATH Keywords

augmented cubedistinguishing numberhypercubesymmetry breaking

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: The distinguishing number of a graph G, denoted D(G), is the minimum number of colors such that there exists a coloring of the vertices of G where no nontrivial graph automorphism is color-preserving. In this paper, we show that the distinguishing number of p-th graph power of the n-dimensional hypercube is 2 whenever 2 < p < n-1. This completes the study of the distinguishing number of hypercube powers. We also compute the distinguishing number of the augmented cube, a variant of the hypercube, answering an open question.

Recommendations

• The distinguishing number of the hypercube
• On distinquishing numbers
• List distinguishing number of \(p^{\text{th}}\) power of hypercube and Cartesian powers of a graph
• Distinguishing Cartesian powers of graphs
• The cost of 2-distinguishing hypercubes

Cites work

• Augmented cubes
• Automorphisms of augmented cubes
• Cartesian powers of graphs can be distinguished by two labels
• Distinguishing Cartesian powers of graphs
• Distinguishing chromatic number of Cartesian products of graphs
• Distinguishing labellings of group action on vector spaces and graphs
• Distinguishing numbers for graphs and groups
• scientific article; zbMATH DE number 731841 (Why is no real title available?)
• On computing the distinguishing numbers of trees and forests
• Symmetry breaking in graphs
• The distinguishing chromatic number
• The distinguishing number of the direct product and wreath product action.
• The distinguishing number of the hypercube
• The maximum distinguishing number of a group

Cited in

(17)

• On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
• The distinguishing number of the hypercube
• Trees with distinguishing index equal distinguishing number plus one
• The distinguishing number of the direct product and wreath product action.
• Symmetry breaking in tournaments
• Generation of Colourings and Distinguishing Colourings of Graphs
• Automorphisms of augmented cubes
• On distinquishing numbers
• Conditional edge-fault pancyclicity of augmented cubes
• The cost number and the determining number of a graph
• Symmetry parameters of various hypercube families
• Fault-Tolerant Panconnectivity of Augmented Cubes AQn
• On the graphs with distinguishing number equal list distinguishing number
• Edge-fault-tolerant vertex-pancyclicity of augmented cubes
• Distinguishing tournaments with small label classes
• Vertex-pancyclicity of augmented cubes with maximal faulty edges
• List distinguishing number of \(p^{\text{th}}\) power of hypercube and Cartesian powers of a graph

This page was built for publication: The distinguishing number of the augmented cube and hypercube powers

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