Measuring the regularity of a graph by its Laplacian eigenvalues

Let {G} be a graph with vertices {1, 2, \dots, n}. The degree of vertex {i} is denoted {d_i}. Let {L} be the Laplacian matrix of {G}, so that {L_{ii}=d_i}, {L_{ij}} is {-1} when the vertices {i, j} are adjacent, and is {0} otherwise. The eigenvalues of {L} are written as {\lambda_1\le \dots \le \lambda_n}.

The graph is regular if all vertices have the same degree: {d_1=\cdots = d_n}. How can this property be seen from its Laplacian eigenvalues {\lambda_1, \dots, \lambda_n}?

Since the sum of eigenvalues is equal to the trace, we have {\sum \lambda_i = \sum d_i}. Moreover, {\sum \lambda_i^2} is the trace of {L^2}, which is equal to the sum of the squares of all entries of {L}. This sum is {\sum d_i^2 + \sum d_i} because the {i}th row of {L} contains one entry equal to {d_i} and {d_i} entries equal to {-1}. In conclusion, {\sum d_i^2 = \sum \lambda_i^2 - \sum\lambda_i}.

The Cauchy-Schwarz inequality says that {n\sum d_i^2 \ge \left(\sum d_i \right)^2} with equality if and only if all numbers {d_i} are equal, i.e., the graph is regular. In terms of eigenvalues, this means that the difference
{\displaystyle D =n\sum d_i^2 - \left(\sum d_i \right)^2 = n\sum (\lambda_i^2 - \lambda_i) - \left( \sum\lambda_i \right)^2 }
is always nonnegative, and is equal to zero precisely when the graph is regular. This is how one can see the regularity of a graph from its Laplacian spectrum.

As an aside, {D } is an even integer. Indeed, the sum {\sum d_i} is even because it double-counts the edges. Hence the number of vertices of odd degree is even, which implies that {\sum d_i^k } is even for every positive integer  {k }.

Up to a constant factor, {D} is simply the degree variance: the variance of the sequence {d_1, \dots, d_n}. What graph maximizes it for a given {n}? We want to have some very large degrees and some very small ones.

Let {G_{m, n}} be the union of the complete graph {K_m} on {m} vertices and {(n-m)} isolated vertices. The sum of degrees is {m(m-1)} and the sum of squares of degrees is {m(m-1)^2}. Hence,

{D = nm(m-1)^2 - (m(m-1))^2 = m(m-1)^2(n-m)}

For {n=3, 4, 5, 6} the maximum is attained by {m=n-1}, that is there is one isolated vertex. For {n=7, 8, 9, 10} the maximum is {m=n-2}. In general it is attained by {m^*=\lfloor (3n+2)/4 \rfloor}.

The graph {G_{m, n}} is disconnected. But any graph has the same degree variance as its complement. And the complement {G^c(m, n)} is always connected: it consists of a “center”, a complete graph on {n-m} vertices, and “periphery”, a set of {m} vertices that are connected to each central vertex. Put another way, {G^c(m, n)} is obtained from the complete bipartite graph {K_{m, n-m}} by connecting all vertices of the {n-m} group together.

Tom A. B. Snijders (1981) proved that {G(m^*, n)} and {G^c(m^*, n)} are the only graphs maximizing the degree variance; in particular, {G^c(m^*, n)} is the unique maximizer among the connected graphs. It is pictured below for {n=4, \dots, 9}.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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