Distinguishing orthogonality graphs. Issue 3 (16th June 2021)

• Record Type: Journal Article
• Authors: Boutin, Debra; Cockburn, Sally
• Is Part Of: Journal of graph theory. Volume 98:Issue 3(2021)
• Page Start: 389
• Page End: 404
• Publication Date: 2021-06-16
• Subjects: determining set -- distinguishing number -- orthogonality graph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22704
• Languages: English
• ISSNs: 0364-9024

Abstract

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 k has 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 − 1 and that, if m 2 ≥ 2 k when k is odd or m 2 ≥ 2 k + 1 when k is even, then 2 < Dist ( Ω 2 k ) ≤ m .