Multidiameters and Multiplicities

The k -diameter of a graph Γ is the largest pairwise minimum distance of a set ofk vertices in Γ, i.e., the best possible distance of a code of size k in Γ. Ak -diameter for some k is called a multidiameter of the graph. We study the function N(k,Δ , D), the largest size of a graph of degree at most Δ 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.