Existence of special graph

Let $G$ be a $n$-vertices graph and $\lambda_1$ is the largest eigenvalue of this graph. If $\lambda_1$ is an integer value, we can easily find the $\lambda_1$- regular graph with $n$ vertices. Now, suppose that $\lambda_1$ is not an integer number (it is a real number). My question is:

Given $\lambda_1$ and $n$, can we construct $G$ (is there such $G$)?

Edit: I think that this question is better.

Let $n$ and $d$ are an odd integers such that $d+1\lt n$. We know that, for each $d$, there exist a graph with largest real eigenvalue $\lambda_1$ which $d \lt\lambda_1 \leq d+1$.

Given $d<\lambda_1'\lt d+1$. Im looking for graph with $\lambda_1$ such that $|\lambda_1 -\lambda_1'|$ be the minimum.

Can I find such graph?

• A graph with $\lambda_1$ an integer need not be regular. There can not be a $31$ vertex graph which is regular of degree $3.$ However there is a tree with $31$ vertices, all eigenvalues integers, and $\lambda_1=3.$ May 20 '16 at 2:35
• I am now confused about which question the respondents are actually answering.... May 21 '16 at 9:58
• @GordonRoyle: I am confused too!!! May 21 '16 at 12:33

3 Answers

I think you mean the adjacency spectrum of simple graph. Since the eigenvalues of graphs are algebraic integers, so the answer to your question is no. For example, the number $\frac{226}{17}$, which is your reputation divided by the number of your medals, is not the largest eigenvalue of any graph.

Also, if you know the largest eigenvalue and the number of vertices of a graph, you can not construct the graph $G$. Since there are cospectral graphs, you may have all eigenvalues of a graph but you can not construct it uniquely.

• Yes, adjacency spectrum is correct. I edit my question. But the existence of graph is important for me, not its uniqueness. May 19 '16 at 17:52
• The existence and construction are two different problems. If you know $\lambda_1$ is an eigenvalue, so the graph exist. If there is such graph and you hope you can construct it, it is not possible. If you know $\lambda_1$ is an eigenvalue of a graph and you just need one such a graph, also the answer is no. I think if you add the largest eigenvalue to the reconstruction problem, again you can not construct the graph. May 19 '16 at 18:01
• I think you mean that the eigenvalues are algebraic integers. May 19 '16 at 18:38
• @RobertIsrael: yes!! May 19 '16 at 19:12

The case that $\lambda_1$ is an integer is not as simple as you think. See the end for a graph with $17$ vertices and $\lambda_1=3.$ There is certainly no regular graph with these properties. (There is an $n$ vertex graph which is regular of degree $d$ exactly when $0 \le d \lt n$ and $nd$ is even.) So start with this special case of your question:

For which integer pairs $d,n$ is there a graph with $n$ vertices and largest eigenvalue $\lambda_1=d?$

If I was forced to guess, then I'd say that for every fixed odd $d \ge 3$ there is an integer $N_d$ such that for every $n \ge N_d$ there is a tree with $n$ vertices and $\lambda_1=d$. I might be totally wrong.

However, here is an example with $n=17$ and $\lambda_1=3.$ It is labelled to show the corresponding eigenvector. The other eigenvalues are $0,\pm 1,\pm 2$ and $-3.$

LATER Here are a few things which can be said. I start with some well known facts (the later ones following from the earlier) and then some general observations. A general point is that it is probably hopeless to find all the possible $\lambda_1$ for a fixed $n$ but much can be said about certain ranges and special values.

Call $G$ and $n,d-$graph if it has $n$ vertices and $\lambda_1=d$

• If $G$ is an $n,d-$graph we can get an $n',d$-Graph for any larger $n'$ by adding isolated vertices. So there is no harm from focusing on connected $n$-vertex graphs although it is convenient to not insist on this.

• If $G$ is a connected $n,d-$graph and we delete any one edge then the new graph will be an $n,d'$-graph with $d' \lt d.$

• A connected graph whose largest vertex degree is $n$ has $\sqrt{n} \le \lambda_1 \le n.$ The upper bound occurs only if the graph is regular and the lower only if it is the $n+1$ vertex star.
• The $n$ vertex path has $\lambda_1=2\cos(\frac{\pi}{n+1}).$ This is approximately $2-(\frac{\pi}{n+1})^2$ for $n$ not too small. This is the least $\lambda_1$ can be for a connected $n$ vertex graph and, as mentioned, it is pretty close to $2$.

• The next smallest values seem likely to come from a path on $n-1$ vertices with an extra edge coming off. I suspect near the middle gives a lower $\lambda_1$ than near the end. It might be the opposite.

• What other $\lambda_1$ are possible below $2?$ A connected graph with a vertex of degree $4$ had $\lambda_1>=2$ with equality only for the star. Also, a connected graph with a cycle as a proper subgraph has $\lambda_1>2.$ All that is left is trees with maximum degree $3.$ Also, if there are two adjacent degree $3$ vertices then $\lambda_1 \ge 2$ with equality only for the $6$ vertex tree (an H).

• The maximum possible is $\lambda_1=n-1$ for the complete graph $K_n$ The next largest is for $K_n$ with one edge deleted. If my calculations are correct, this has $\lambda_1=\frac{n-3+\sqrt{n^2+2-7}}2 \approx n-1-\frac{2}n.$ There are two ways to remove two edges and perhaps five ways to remove three edges. This makes it seem possible to find the $10$ largest possible values although it rapidly becomes tedious.

• Similarly, if $nd$ is even and $d \lt n-1$ then there are regular graphs with $\lambda_1=d$, there may also be non-regular ones. adding or deleting an edge seems promising for finding nearby values of $\lambda_1.$ I will wildly guess that the first possible value after $2$ comes from a triangle with a long tail hanging off. However the cases of a trees also need investigation.

Since there are only finitely many graphs with $n$ vertices, in principle you can just do a brute-force search over these graphs. If one with largest eigenvalue $\lambda_1$ exists, you will find it, otherwise you will prove such a graph does not exist. Of course, this is not practical unless $n$ is small.