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:

6 vertices, max degree 4, with a = 4
7 vertices, max degree 4, with a = 3.2

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.

8 vertices, max degree 4, with a = 4

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 }:

5 vertices, max degree 3, with a = 2

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:

9 vertices, max degree 5, with a = 4

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”.

8 vertices, max degree 3, with a = 2
8 vertices, max degree 3, with a = 2

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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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