The cost of 2-distinguishing hypercubes

DOI10.1016/J.DISC.2021.112512zbMATH Open1467.05219arXiv2007.15948OpenAlexW3176937098MaRDI QIDQ2037589FDOQ2037589

Authors: Debra L. Boutin 

Publication date: 8 July 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A graph $G$ is said to be {it $2$-distinguishable} if there is a labeling of the vertices with two labels so that only the trivial automorphism preserves the labels. The minimum size of a label class, over all 2-distinguishing labelings, is called the {it cost of $2$-distinguishing}, denoted by $ho(G)$. For $ngeq4$ the hypercubes $Q_n$ are 2-distinguishable, but the values for $ho(Q_n)$ have been elusive, with only bounds and partial results previously known. This paper settles the question. The main result can be summarized as: for $ngeq4$, $ho(Q_n)in1+lceillo{g}_{2}nceil,2+lceillo{g}_{2}nceil$. Exact values are be found using a recursive relationship involving a new parameter $u_m$, the smallest integer for which $ho(Q_{u_m})=m$. The main result is�egin{gather*} 4leq n leq 12Longrightarrow ho(Q_n)=5, ext{ and } 5leq m leq 11 Longrightarrow

u_m=4; \ ext{ for } mgeq 6, ho(Q_n) = m iff 2^{m-2} - u_{m-1} + 1 leq n leq 2^{m-1}- u_m; \ ext{ for } ngeq 5,

u_m = n iff 2^{n-1} - ho(Q_{n-1}) + 1leq m leq 2^{n}- ho(Q_n).end{gather*}

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

Recommendations

• Small label classes in 2-distinguishing labelings
• The cost of 2-distinguishing selected Kneser graphs and hypercubes
• The cost of 2-distinguishing Cartesian powers
• The distinguishing number of the hypercube
• On distinquishing numbers

zbMATH Keywords

hypercubesdetermining numbergraph distinguishingdistinguishing cost

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Symmetry breaking in graphs
• Handbook of product graphs
• Distinguishability of locally finite trees
• Distinguishing infinite graphs
• Distinguishability of infinite groups and graphs
• The cost of 2-distinguishing selected Kneser graphs and hypercubes
• Small label classes in 2-distinguishing labelings
• Using determining sets to distinguish Kneser graphs
• The cost of distinguishing graphs
• Distinguishing Cartesian powers of graphs
• Distinguishing Cartesian powers of graphs
• Cartesian powers of graphs can be distinguished by two labels
• The distinguishing number of the hypercube
• 3-connected planar graphs are 2-distinguishable with few exceptions
• The determining number of a Cartesian product
• The cost of 2-distinguishing Cartesian powers

Cited In (7)

• The cost of 2-distinguishing selected Kneser graphs and hypercubes
• Symmetry parameters of various hypercube families
• The distinguishing number of the augmented cube and hypercube powers
• Paint cost and the frugal distinguishing number
• Small label classes in 2-distinguishing labelings
• The cost of 2-distinguishing Cartesian powers
• The distinguishing number of the hypercube

This page was built for publication: The cost of 2-distinguishing hypercubes

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