Premium
Distinguishing orthogonality graphs
Author(s) -
Boutin Debra,
Cockburn Sally
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22704
Subject(s) - combinatorics , mathematics , orthogonality , graph , automorphism , automorphism group , wheel graph , independent set , enhanced data rates for gsm evolution , discrete mathematics , graph power , line graph , computer science , geometry , telecommunications
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 set of vertices S ⊆ V ( G ) 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 Ω 2 khas vertices which are bitstrings of length 2 k with an edge between two vertices if they differ in precisely k bits. This paper shows that Det ( Ω 2 k ) = 2 2 k − 1and that, ifm 2 ≥ 2 k when k is odd orm 2 ≥ 2 k + 1 when k is even, then 2 < Dist ( Ω 2 k ) ≤ m .