# Maximal algebraic connectivity among graphs of bounded degree

The algebraic connectivity ${ a(G) }$ of a graph ${G }$ is its smallest nontrivial Laplacian eigenvalue. Equivalently, it is the minimum of edge sums ${\sum_{e\in E} df(e)^2}$ over all functions ${f\colon V\to\mathbb R}$ normalized by ${ \sum_{v\in V} f(v) = 0 }$ and ${\sum_{v\in V} f(v)^2 = 1 }$. Here  ${ V, E }$ are vertex/edge sets, and ${ df(e)}$ means the difference of the values of ${f }$ at the vertices of the edge ${ e}$.

It is clear from the definition that adding edges to ${ G}$ cannot make  ${a(G) }$ smaller; thus, among all graphs on ${n }$ vertices the maximal value of ${a(G) }$ is attained by the complete graph, for which ${a(G) = n}$. For any other graph ${ a(G)\le n-2}$ which can be shown as follows. Pick two non-adjacent vertices ${u }$ and ${v }$ and let ${f(u)=1/\sqrt{2} }$, ${ f(v) = -1/\sqrt{2}}$, and ${f=0 }$ elsewhere. This function is normalized as required above, and its edge sum ${\sum_{e\in E} df(e)^2}$ is at most ${ n-2}$ since there are at most ${ 2(n-2)}$ edges with a nonzero contribution.

What if we require the graph to have degree vertex at most ${d}$, and look for maximal connectivity then? First of all, only connected graphs are under consideration, since ${a(G)=0}$ for non-connected graphs. Also, only the cases ${n\ge d+2 }$ are of interest, otherwise the complete graph wins. The argument in the previous paragraph shows that ${ a(G) \le d}$ but is this bound attained?

The case ${d=2}$ is boring: the only two connected graphs are the path ${P_n}$ and the cycle ${ C_n}$. The cycle wins with  ${a(C_n) = 2(1-\cos(2\pi/n)) }$ versus ${ a(P_n) = 2(1-\cos(\pi/n))}$.

When ${ d=4}$, one might suspect a pattern based on the following winners:

The structure of these two is the same: place ${n }$ points on a circle, connect each of them to ${4 }$ nearest neighbors.

But this pattern does not continue: the 8-vertex winner is completely different.

This is simply the complete bipartite graph ${ K_{4, 4} }$. And it makes sense that the “4 neighbors” graph loses when the number of vertices is large: there is too much “redundancy” among its edges, many of which connect the vertices that were already connected by short paths.

In general, when ${n = 2d }$, the complete bipartite graph ${ K_{d, d}}$ achieves ${a = d }$ and therefore maximizes the algebraic connectivity. The fact that ${a(K_{d, d}) = d }$ follows by considering graph complement, as discussed in Laplacian spectrum of small graphs. The complement of ${K_{d, d} }$ is the disjoint union of two copies of the complete graph ${K_d }$, for which the maximal eigenvalue is ${d }$. Hence ${a(G) = n - \lambda_{\max}(G^c) = n-d = d }$.

When ${ n = 2d-1}$ is odd, we have a natural candidate in ${ K_{d,d-1}}$ for which the argument from the previous paragraph shows ${a(G) = d-1 }$. This is indeed a winner when ${n=5, d=3 }$:

The winner is not unique since one can add another edge between two of the vertices of degree 2. This does not change the ${a(G)}$, however: there is a fundamental eigenfunction that has equal values at the vertices of that added edge.

Same for ${n=9, d=5 }$: the complete bipartite graph shares the maximum value of algebraic connectivity with two other graphs formed by adding edges to it:

However, the family ${ K_{d,d-1}}$ does not win the case ${ n = 2d-1}$ in general: we already saw a 4-regular graph on 7 vertices with ${a(G)\approx 3.2 }$, beating ${ a(K_{4, 3}) = 3}$. Perhaps ${ K_{d,d-1}}$ wins when ${ d}$ is odd?

I do not have any other patterns to conjecture, but here are two winners for ${ n = 8, d= 3}$: the cube and the “twisted cube”.

The cube is twisted by replacing a pair of edges on the top face with the diagonals. This is still a 3-regular graph and the algebraic connectivity stays the same, but it is no longer bipartite: a 5-cycle appears.

This site uses Akismet to reduce spam. Learn how your comment data is processed.