Bounds on Codes Based on Graph Theory
| dc.creator | Rouayheb, Salim Y. El | |
| dc.creator | Georghiades, C. N. | |
| dc.creator | Soljanin, E. | |
| dc.creator | Sprintson, A. | |
| dc.date | 2008-06-30 | |
| dc.date.accessioned | 2026-07-07T09:47:31Z | |
| dc.date.available | 2026-07-07T09:47:31Z | |
| dc.description | 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 Erdős-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. | |
| dc.identifier | https://arxiv.org/abs/0806.4979 | |
| dc.identifier | http://arxiv.org/abs/0806.4979 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/163911 | |
| dc.subject | Information Theory | |
| dc.title | Bounds on Codes Based on Graph Theory | |
| dc.type | text |