Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

Diameters and eigenvalues


Author: F. R. K. Chung
Journal: J. Amer. Math. Soc. 2 (1989), 187-196
MSC: Primary 05C50; Secondary 05C38
MathSciNet review: 965008
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We derive a new upper bound for the diameter of a $ k$-regular graph $ G$ as a function of the eigenvalues of the adjacency matrix. Namely, suppose the adjacency matrix of $ G$ has eigenvalues $ {\lambda _1},{\lambda _2}, \ldots ,{\lambda _n}$ with $ \left\vert {{\lambda _1}} \right\vert \geq \left\vert {{\lambda _2}} \right\vert \geq \cdots \geq \left\vert {{\lambda _n}} \right\vert$ where $ {\lambda _1} = k$, $ \lambda = \left\vert {{\lambda _2}} \right\vert$. Then the diameter $ D(G)$ must satisfy

$\displaystyle D(G) \leq \left\lceil {\log (n - 1)/{\text{log}}(k/\lambda )} \right\rceil $

.

We will consider families of graphs whose eigenvalues can be explicitly determined. These graphs are determined by sums or differences of vertex labels. Namely, the pair $ \left\{ {i,j} \right\}$ being an edge depends only on the value $ i + j$ (or $ i - j$ for directed graphs). We will show that these graphs are expander graphs with small diameters by using an inequality on character sums, which was recently proved by N. M. Katz.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 05C50, 05C38

Retrieve articles in all journals with MSC: 05C50, 05C38


Additional Information

DOI: http://dx.doi.org/10.1090/S0894-0347-1989-0965008-X
PII: S 0894-0347(1989)0965008-X
Article copyright: © Copyright 1989 American Mathematical Society