Bounds on Codes Based on Graph Theory Academic Article uri icon


  • Let A q (n,d) be the maximum order (maximum number of codewords) of a q-ary code of length n and Hamming distance at least d. And let A(n, d, w) that of a binary code of constant weight w. Building on results from algebraic graph theory and Erdos-ko-Rado like theorems in extremal combinatorics, we show how several known bounds on A q (n, d) and A(n, d, w) can be easily obtained in a single framework. For instance, both the Hamming and Singleton bounds can derived as an application of a property relating the clique number and the independence number of vertex transitive graphs. Using the same techniques, we also derive some new bounds and present some additional applications. ©2007 IEEE.

author list (cited authors)

  • Rouayheb, S., Georghiades, C. N., Soljanin, E., & Sprintson, A.

citation count

  • 8

publication date

  • June 2007