Distinguishing orthogonality graphs

Autor: Debra L. Boutin, Sally Cockburn
Rok vydání: 2021
Předmět:
Zdroj: Journal of Graph Theory. 98:389-404
ISSN: 1097-0118
0364-9024
DOI: 10.1002/jgt.22704
Popis: 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
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje