A Note on the Stability Number of an Orthogonality Graph

E. de Klerk, D.V. Pasechnik

Research output: Working paperDiscussion paperOther research output

325 Downloads (Pure)


We consider the orthogonality graph (n) with 2n vertices corresponding to the vectors {0, 1}n, two vertices adjacent if and only if the Hamming distance between them is n/2.We show that, for n = 16, the stability number of (n) is ( (16)) = 2304, thus proving a conjecture by Galliard [7].The main tool we employ is a recent semidefinite programming relaxation for minimal distance binary codes due to Schrijver [16].Moreover, we give a general condition for Delsarte bound on the (co)cliques in graphs of relations of association schemes to coincide with the ratio bound, and use it to show that for (n) the latter two bounds are equal to 2n/n.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages11
Publication statusPublished - 2005

Publication series

NameCentER Discussion Paper


  • C0
  • C61


Dive into the research topics of 'A Note on the Stability Number of an Orthogonality Graph'. Together they form a unique fingerprint.

Cite this