论文标题
区分正交图
Distinguishing Orthogonality Graphs
论文作者
论文摘要
如果有$ d $标签的顶点标签，则图$ g $可以是$ d $ distance，因此只有琐碎的自动形态保留标签。最小的$ d $是区分数字（$ g $）。如果$ g $的每一个自动形态由$ s $唯一决定，则顶点$ s $的子集是$ g $的确定集。 $ g $的最小确定集的大小称为确定号码，det（$ g $）。正交图$ω_{2K} $具有长度为$ 2K $的bitsing $，如果两个顶点之间的边缘在两个顶点之间，则在$ k $ bit上有所不同。本文表明，det（$ω_{2k} $）$ = 2^{2k-1} $，如果$ \ binom {m} {2} {2} {2} \ geq 2k $，则$ 2 <$ dist（$ω__{2k} $）$ \ leq m $。
A graph $G$ is said to be $d$-distinguishable if there is a labeling of the vertices with $d$ labels so that only the trivial automorphism preserves the labels. The smallest such $d$ is the distinguishing number, Dist($G$). A subset of vertices $S$ is a determining set for $G$ if every automorphism of $G$ is uniquely determined by its action on $S$. The size of a smallest determining set for $G$ is called the determining number, Det($G$). The orthogonality graph $Ω_{2k}$ has vertices which are bitstrings of length $2k$ with an edge between two vertices if they differ in precisely $k$ bits. This paper shows that Det($Ω_{2k}$) $= 2^{2k-1}$ and that if $\binom{m}{2} \geq 2k$ then $2<$ Dist($Ω_{2k}$) $\leq m$.
