8
$\begingroup$

While doodling recently I found that the largest eigenvalue of the adjacency matrix of the following undirected graph (ignore directions on edges in picture) is "almost" $\pi$. According to octave its largest eigenvalue is 3.1413. FWIW, its exact answer is 1+2$w$ where $w$ is the largest root of $4w^3+4w^2-7w-2=0$, which WolframAlpha evaluates as 3.141336114.

So my question is, is there a graph whose largest eigenvalue of its AM is closer to -- but not equal to -- $\pi$?

Many thanks.

this

$\endgroup$
0

1 Answer 1

3
$\begingroup$

A possibility is to start with a huge $3$-regular graph $G_{2n}$ with $2n$ vertices then joining couples of vertices with degree $3$ (the degree of any vertex in such a couple goes from $3$ to $4$) with an edge. Each time we add an edge, the dominating eigenvalue eigenvalue slowly increases, going from $3$ to $4$ (if we add $n$ edges, we get a $4$-regular graph). Since $n$ is arbitrary, there is a class of graphs with the dominating eigenvalue arbitrarily close to $\pi$, as wanted.

The depicted graph is, indeed, an almost-$3$-regular graph: only a vertex out of $9$ has degree $4$, hence we may expect to have the dominating eigenvalue close to $3+\frac{1}{9}=3.111\ldots\approx\pi.$

For the same reason, the following graph is another good candidate: The PiGraph

I think that a really interesting problem is to exhibit an infinite graph with dominating eigenvalue exactly equal to $\pi$; I think it is not too difficult to prove, through a combinatorial compactness argument, that such a graph must exist, but maybe it has a "nice" structure, too.

$\endgroup$
1
  • $\begingroup$ Nice construction. Apologies for delay in responding. $\endgroup$
    – healyp
    Oct 1, 2014 at 10:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .