Spectrum of Complete Graphs

Question

What properties may be deduced from the spectrum of complete graphs such as number of edges or regularity?

Answer 1

It is usually more advisable to say you know the spectrum of the graph and some little bit of auxiliary data about the graph itself. For example, if you know the graph is d-regular and you know the spectrum, then you get the Cheeger inequality which says

$$ \frac{1}{2} (d - \lambda_2) \leq h(G) \leq \sqrt{2d(d-\lambda_2)} $$

So imagine you don't have the graph, but only $\lambda_2$, but someone assured you yes it is is d-regular. Depending on the precision, this could be a lot less data than specifying the entire graph. It is the number of bits to encode $\lambda_2$ vs something like $V^2$ to specify the edges. But even without the graph, you still learn something about $h(G)$.

You can't expect everything without that little bit of extra information. That is because the spectrum is not a complete invariant. You can't just take the spectrum and know all the isomorphism invariant properties of the graph. That is because there are non-isomorphic but still cospectral graphs. But if you give a little bit of extra information about the graph, then the spectrum can be enough to give the properties that you really want, possibly even all of them.

Like if you are told that the graph is a finite starlike tree on some number of vertices, but you aren't told how big or how the tree is arranged.