Name
Abstract | ||
|---|---|---|
The k-diameter of a graph Gamma is the largest pairwise minimum distance of a set of k vertices in Gamma, i.e., the best possible distance of a code of size k in Gamma. A k-diameter for some k is called a multidiameter of the graph. We study the function N (k, Delta, D), the largest size of a graph of degree at most a and k-diameter D. The graphical analogues of the Gilbert bound and the Hamming bound in coding theory are derived. Constructions of large graphs with given degree and k-diameter are given. Eigenvalue upper bounds are obtained. By combining sphere packing arguments and eigenvalue bounds, new lower bounds on spectral multiplicity are derived. A bound on the error coefficient of a binary code is given. (C) 1999 Academic Press. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1006/eujc.1999.0311 | Eur. J. Comb. |
Keywords | Field | DocType |
coding theory,upper bound,eigenvalues,sphere packing,lower bound | Discrete mathematics,Combinatorics,Bound graph,Vertex (geometry),Upper and lower bounds,Sphere packing,Binary code,Coding theory,Hamming bound,Mathematics,Eigenvalues and eigenvectors | Journal |
Volume | Issue | ISSN |
20 | 7 | 0195-6698 |
Citations | PageRank | References |
1 | 0.37 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fan Chung | 1 | 30 | 2.98 |
| Charles Delorme | 2 | 43 | 23.16 |
| Patrick Solé | 3 | 48 | 12.83 |