Spectral Graph Theory

179 Views Asked by At

Let $\lambda_1, \lambda_2, ..., \lambda_t$ be distinct real values. Let $X = \{\lambda_1, \lambda_2, ..., \lambda_t\}$. Prove that there are finite number of connected graphs $G$ such that spectrum of $G$ without algebraic multiplicity is equal to $X$. In other words, each eigenvalue of $G$ belongs to $X$ and each member of $X$ is an eigenvalue of $G$.

My approach was to use the fact that $diam(G) <= t-1$ (This is a well-known fact that bounds diameter of a graph to the number of its distinct eigenvalues). I tried to show that there is a bound $N$ on the number of vertices of any such graph with above property but I failed. One obvious fact is that $|E(G)|$ is bounded by $\frac{n \times \max{\lambda_i^2}s}{2}$ which is of $O(n)$ but this didn't help me either.

Any hints and/or ideas are highly appreciated.

1

There are 1 best solutions below

0
On

Suppose $G_1,G_2,\ldots$ is an infinite sequence of connected graphs such $|V(G_i)| < |V(G_{i+1})|$ and such that the set of the eigenvalues of $G_i$ is $X = \{\lambda_1,\ldots, \lambda_t\}$ for all $i$.

Let $\lambda$ be the largest eigenvalue in $X$. Then it is well known that

$$\Delta(G_i) \leq \lambda^2\,$$ and hence the graphs in our sequence have bounded degree. But then the sequence of graphs have unbounded diameter (see also this) and hence there exist an $i$ such that $\rm{diam}(G_i) \geq t$ and hence $G_i$ has to have at least $t+1$ distinct eigenvalues thus deriving a contradiction.