I’ve decided not to port over the posts from AoPS. Among other things, I’d prefer to preserve the comments on older posts as they are.
So here’s something I’ve been thinking about. Given a simple connected graph , define to be its largest positive eigenvalue; in other words, if counts the number of walks (equivalently, closed walks) of length on , then
(The limit of the ratio between consecutive terms won’t work if, for example, is bipartite.) There are a couple of ways to see that the largest positive eigenvalue also bounds the absolute value of the negative eigenvalues: one is by the Perron-Frobenius theorem, but really it suffices to observe that is always a non-negative integer. Hence is the spectral radius of the adjacency matrix.
For most graph theorists, it’s more natural to talk about the spectral radius of the Laplacian, and there appears to be a general consensus that the Laplacian is both more interesting and more useful. But I’ve always had a soft spot for the adjacency matrix, so this is what this post is going to be about. Recently I’ve been playing around with small values of the spectral radius.
Property 1: The spectral radius of an undirected graph cannot lie in .
Proof. If has no edges, we are done. Suppose no two edges of are incident to the same vertex; then the number of closed walks of length is zero if is odd and twice the number of edges if is even; thus the only eigenvalues are and .
Now suppose there are two edges incident to the same vertex.
Lemma (subgraph bound): Let be a graph, and let be a subgraph of . Then .
Proof. Every (closed) walk on is a (closed) walk on .
Back to Property 1. Now, the graph consisting of two edges connecting three vertices is the path graph , and its eigenvalues are , which one can see as follows: the number of closed walks of length from the center vertex to itself is if is odd and if is even, since a closed walk is just a choice of which of the two other vertices to visit every other step. It follows that .
More generally, it turns out that the subgraph bound implies that spectral radii are discretized, at least up to a point.
Property 2: The only connected simple graphs with are the path graphs .
Proof. The star graph satisfies , which is easily verified by counting the number of closed walks from the center vertex to itself. It follows by the subgraph bound that a graph with has no vertices of degree . Similarly, the cycle graphs all satisfy , since they are -regular, so by the subgraph bound is acyclic. These two conditions ensure that consists of a single path graph . (Note that .)
The path graphs satisfy , which we will not prove here. It turns out that the characteristic polynomials of the corresponding adjacency matrices are the Chebyshev polynomials of the second kind, which is quite interesting in its own right, but that’s another story. Since , it follows that .
The above proof actually had to prove something stronger: if a graph with is acyclic, we might ask if this discreteness in the behavior of the spectral radius continues to hold at least up to radius . We can’t hope for discreteness after , since the path graphs satisfy but ; in other words, is a limit point of the set of spectral radii. But we can prove that there aren’t any smaller ones.
Property 3: For every , the set of connected simple graphs with is finite.
The following lemma will be useful.
Lemma: If is a connected simple graph with , then is a binary tree.
Proof. We know that must be acyclic. The graph on five vertices consisting of a vertex of degree and four other vertices also has spectral radius : the number of closed walks of length from the center vertex to itself is if is odd and if is even. Again, it follows by the subgraph bound that the vertices of have degree at most . (If we fix a root not of degree , we obtain the usual “picture” of a binary tree.)
Back to Property 3. Let be a binary tree and fix a root (which can be any vertex not of degree ). If , then there exists such that cannot contain as a subgraph. Quantitatively, since
it follows that the largest value of such that can contain as a subgraph satisfies
So as a binary tree has height at most . But a binary tree of height has at most vertices, so there are finitely many such graphs. This also implies that the set of their spectral radii is finite.
So here are some questions:
1. The proof above shows that the maximum number of vertices of a graph with is , which is probably a very loose bound. What is a sharp bound? What is a bound on the number of (labeled) connected simple graphs with this property?
2. The sequence of spectral radii less than begins . Does it have interesting properties? (I am thinking of a vague analogy with the Beraha constants.)
3. The characteristic polynomial of a symmetric matrix with integer coefficients is monic with integer coefficients, and in addition all of its roots are real. I have been told that not every such polynomial occurs as the characteristic polynomial of a symmetric matrix; to what extent is this for “graph-theoretic” reasons? Put another way, to what extent are the above results true for any monic polynomial with integer coefficients and real roots? (“Spectral radius” should be interpreted as meaning the largest root in absolute value.)