Distinguishing Orthogonality Graphs

Abstract

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 $\left(\genfrac{}{}{0ex}{}{m}{2}\right)\ge 2k$ then $2<$ Dist(${\Omega }_{2k}$) $\le m$.

17 pages, 5 figures

References in corpus (4)

• The cost of exactly simulating quantum entanglement with classical communication
• Distinguishing number and distinguishing index of neighbourhood corona of two graphs
• Distinguishing Numbers and Generalizations
• Distinguishing Number of Non-Zero Component Graphs