标题： 区分正交性图 显示英文标题

标题： Distinguishing Orthogonality Graphs

摘要： 一个图$G$被称为$d$-可区分的，如果用$d$个标签对顶点进行标记，使得只有恒等自同构能保持标签不变。 最小的这样的$d$是区分数，Dist($G$)。 顶点的一个子集$S$是$G$的确定集，如果$G$的每个自同构均由其在$S$上的作用唯一确定。 $G$的最小确定集的大小称为确定数，Det($G$)。 正交性图 $\Omega_{2k}$ 的顶点是长度为 $2k$ 的位串，如果两个顶点恰好在 $k$ 位上不同，则它们之间有一条边。 本文表明 Det($\Omega_{2k}$) $= 2^{2k-1}$，并且如果 $\binom{m}{2} \geq 2k$ 则$2<$ Dist($\Omega_{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 $\Omega_{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($\Omega_{2k}$) $= 2^{2k-1}$ and that if $\binom{m}{2} \geq 2k$ then $2<$ Dist($\Omega_{2k}$) $\leq m$.