2020/07/31 by Boutin, Debra · 1 citation
#05C15 #05C25 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2007.15948
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 ρ(G). For n≥ 4 the hypercubes Qn are 2-distinguishable, but the values for ρ(Qn) have been elusive, with only bounds and partial results previously known. This paper settles the question. The main result can be summarized as: for n≥ 4, ρ(Qn) ∈ \1+\lceil log2 n \rceil, 2 + \lceil log2 n\rceil\. Exact values are be found using a recursive relationship involving a new parameter νm, the smallest integer for which ρ(Qνm)=m. The main result is4≤ n ≤ 12\Longrightarrow ρ(Qn)=5, and 5≤ m ≤ 11 \Longrightarrow νm=4;
for m≥ 6, ρ(Qn) = m \iff 2m-2 - νm-1 + 1 ≤ n ≤ 2m-1-νm;
for n≥ 5, νm = n \iff 2n-1 - ρ(Qn-1) + 1≤ m ≤ 2n-ρ(Qn).