Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph

Abstract: The Hamming graph

H (n, q)

is the graph whose vertices are the words of length

n

over the alphabet

0, 1, l d o t s, q - 1

, where two vertices are adjacent if they differ in exactly one coordinate. The adjacency matrix of

H (n, q)

has

n + 1

distinct eigenvalues

n (q - 1) - q c d o t i

with corresponding eigenspaces

U_{i} (n, q)

for

0 l e q i l e q n

. In this work we study functions belonging to a direct sum

U_{i} (n, q) o p l u s U_{i + 1} (n, q) o p l u s l d o t s o p l u s U_{j} (n, q)

for

0 l e q i l e q j l e q n

. We find the minimum cardinality of the support of such functions for

q = 2

and for

q = 3

,

i + j > n

. In particular, we find the minimum cardinality of the support of eigenfunctions from the eigenspace

U_{i} (n, 3)

for

i > f r a c n 2

. Using the correspondence between

1

-perfect bitrades and eigenfunctions with eigenvalue

- 1

, we find the minimum size of a

1

-perfect bitrade in the Hamming graph

H (n, 3)

.

Recommendations

Cites Work

Cited In (12)

This page was built for publication: Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph