论文标题
2-距离区分超管的成本
The Cost of 2-Distinguishing Hypercubes
论文作者
论文摘要
如果有两个标签的顶点标签，则据说$ g $ {\ it $ 2 $ - distanclable}，以便只有微不足道的自动形态保留标签。在所有2端分辨标签上，标签类的最小尺寸称为{\ it成本为$ 2 $ -DISTONDICAINS}，用$ρ（g）$表示。对于$ n \ geq 4 $，hyperucubes $ q_n $是2固定的，但是$ρ（q_n）$的值是难以捉摸的，只有以前已知的界限和部分结果。本文解决了问题。主要结果可以总结为：对于$ n \ geq 4 $，$ρ（q_n）\ in \ {1+ \ lceil \ log_2 n \ rceil，2 + \ lceil \ log_2 n \ rceil \ rceil \} $。使用涉及新参数$ν_m$的递归关系找到了精确的值，这是$ρ（q_ {ν_m}）= m $的最小整数。主要结果是\ begin {chater*} 4 \ leq n \ leq 12 \longrightArrowρ（q_n）= 5，\ text {and} 5 \ leq m \ leq m \ leq 11 \longrightArrowν_m= 4; \\ \ text {for} m \ geq 6，ρ（q_n）= m \ iff 2^{m-2} - ν_{m-1} + 1 \ leq n \ leq n \ leq 2^{m-1} {m-1} {m-1}-ν_m; \\ \ text {for} n \ geq 5，ν_m= n \ iff 2^{n-1} - ρ（q_ {n-1}） + 1 \ leq m \ leq m \ leq 2^{n} {n} - ρ（q_n）。
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\geq 4$ the hypercubes $Q_n$ are 2-distinguishable, but the values for $ρ(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 $n\geq 4$, $ρ(Q_n) \in \{1+\lceil \log_2 n \rceil, 2 + \lceil \log_2 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 is\begin{gather*} 4\leq n \leq 12\Longrightarrow ρ(Q_n)=5, \text{ and } 5\leq m \leq 11 \Longrightarrow ν_m=4; \\ \text{ for } m\geq 6, ρ(Q_n) = m \iff 2^{m-2} - ν_{m-1} + 1 \leq n \leq 2^{m-1}-ν_m; \\ \text{ for } n\geq 5, ν_m = n \iff 2^{n-1} - ρ(Q_{n-1}) + 1\leq m \leq 2^{n}-ρ(Q_n).\end{gather*}
