TY - JOUR

T1 - Disconnected vertex sets and equidistant code pairs

AU - Haemers, Willem H.

PY - 1997/1/1

Y1 - 1997/1/1

N2 - Two disjoint subsets A and B of a, vertex set V of a finite graph G are called disconnected if there is no edge between A and B. If V is the set of words of length n over an alphabet {1, . . . , q} and if two words are adjacent whenever their Hamming distance is not equal to a fixed δ ∈ {1, . . . , n}, then a pair of disconnected sets becomes an equidistant code pair. For disconnected sets A and B we will give a bound for |A| · |B| in terms of the eigenvalues of a matrix associated with G. In case the complement of G is given by a relation of an association scheme the bound takes an easy form, which applied to the Hamming scheme leads to a bound for equidistant code pairs. The bound turns out to be sharp for some values of q, n and δ, and for q → ∞ for any fixed n and δ. In addition, our bound reproves some old results of Ahlswede and others, such as the maximal value of |A| · |B| for equidistant code pairs A ans B in the binary Hamming Scheme.

AB - Two disjoint subsets A and B of a, vertex set V of a finite graph G are called disconnected if there is no edge between A and B. If V is the set of words of length n over an alphabet {1, . . . , q} and if two words are adjacent whenever their Hamming distance is not equal to a fixed δ ∈ {1, . . . , n}, then a pair of disconnected sets becomes an equidistant code pair. For disconnected sets A and B we will give a bound for |A| · |B| in terms of the eigenvalues of a matrix associated with G. In case the complement of G is given by a relation of an association scheme the bound takes an easy form, which applied to the Hamming scheme leads to a bound for equidistant code pairs. The bound turns out to be sharp for some values of q, n and δ, and for q → ∞ for any fixed n and δ. In addition, our bound reproves some old results of Ahlswede and others, such as the maximal value of |A| · |B| for equidistant code pairs A ans B in the binary Hamming Scheme.

UR - http://www.scopus.com/inward/record.url?scp=53249123348&partnerID=8YFLogxK

U2 - 10.37236/1292

DO - 10.37236/1292

M3 - Article

AN - SCOPUS:53249123348

VL - 4

SP - XXI-XXII

JO - The Electronic Journal of Combinatorics: EJC

JF - The Electronic Journal of Combinatorics: EJC

SN - 1097-1440

IS - 1

ER -