Fast Consensus Topology Design via Minimizing Laplacian Energy

Over the past two decades, consensus has achieved great success and attracted significant attention [1, 2, 3, 4], being applied to a wide range of distributed control and computation problems [5, 6, 7, 8].

A continuous-time linear consensus process over a simple connected graph $\mathbb{G}$ can be typically modeled by a linear differential equation of the form $\dot{x}(t)=-Lx(t)$, where $x(t)$ is a vector in ${\rm I\!R}^{n}$ and $L$ is the “Laplacian matrix” of $\mathbb{G}$. For any simple graph $\mathbb{G}$ with $n$ vertices, we use $D(\mathbb{G})$ and $A(\mathbb{G})$ to denote its degree matrix and adjacency matrix, respectively. Specifically, $D(\mathbb{G})$ is an $n\times n$ diagonal matrix whose $i$th diagonal entry equals the degree of vertex $i$, and $A(\mathbb{G})$ is an $n\times n$ matrix whose $ij$th entry equals 1 if $(i,j)$ is an edge in $\mathbb{G}$ and otherwise equals 0. The Laplacian matrix of $\mathbb{G}$ is defined as $L(\mathbb{G})=D(\mathbb{G})-A(\mathbb{G})$. It is easy to see that any Laplacian matrix is symmetric and thus has a real spectrum. It is well known that $L(\mathbb{G})$ is positive-semidefinite, its smallest eigenvalue equals 0, and its second smallest eigenvalue, called the algebraic connectivity of $\mathbb{G}$ and denoted as $a(\mathbb{G})$, is positive if and only if $\mathbb{G}$ is connected [9]. It has been shown that the convergence rate of continuous-time linear consensus is determined by the algebraic connectivity, in that the larger the algebraic connectivity is, the faster the consensus can be reached [2].

With the preceding facts in mind, a natural and fundamental research problem is how to design network topology to achieve faster or even the fastest consensus. The problem has been studied for many years [10, 11, 12, 13, 14, 15], to name a few. Notwithstanding these developments, the following question is still largely unsolved: Given a fixed number of vertices and edges, what are the optimal graphs that achieve maximal algebraic connectivity?

The above question presents a challenging combinatorial optimization problem, and thus, it was only partially answered for some special cases in [15]. Even though a powerful computer can execute such a combinatorial search, identifying the graphical properties of optimal graphs with maximal algebraic connectivity remains a mystery, not to mention the associated computational complexity.

In this paper, we propose approximating the maximal algebraic connectivity by minimizing the “Laplacian energy” defined as follows.

The above concept was first proposed in [16] and finds applications/connections to ordinary energy for $\pi$-electron energy in molecules [17] and the first Zagreb index [18]. It is worth mentioning that there have been various mathematical definitions for network energy [19], including the earliest version of Laplacian energy [20].

We are motivated to appeal to the concept of Laplacian energy for designing fast/optimal consensus network topologies due to the following observations: We list all maximal algebraic connectivity graphs under the constraint of fixed numbers of vertices and edges for the cases where the vertex number $n$ ranges from 4 to 7. These are respectively given in Figures 1 through 4.¹¹1The maximal algebraic connectivity graphs depicted in Figures 2 through 4 are sourced from [15]. We omit the case of $n=3$ as well as some complete graphs, as these graphs are unique. For $n\geq 8$, it will be very computationally expensive to go through all possible graphs. For each of these graphs, we list its corresponding Laplacian energy $E$, and for each pair of vertex number $n$ and edge number $m$, we list the minimal Laplacian energy $E_{{\rm min}}$ among all possible graphs. It is readily apparent that among all simple graphs with a fixed number of vertices and edges, maximal algebraic connectivity and minimal Laplacian energy coincide in most cases. The non-matching cases, highlighted in orange, are always centered in sparse cases and occasionally scattered in medium-density cases. This suggests that we may design fast consensus topologies by minimizing Laplacian energy for most scenarios. It turns out that, given a fixed number of vertices and edges, minimizing Laplacian energy is a much easier task and considerably more computationally efficient.

In this paper, we first characterize the degree distribution properties of minimal Laplacian energy graphs under the constraint of fixed numbers of vertices and edges, and then devise an algorithm to construct such connected optimal graphs (cf. Section II). Next, we show that the minimal Laplacian energy graphs generated by the proposed algorithm exhibit strong resilience, featuring maximum vertex and edge connectivity (cf. Section III). Finally, we investigate the spectral properties of the Laplacian matrices of these generated minimal Laplacian energy graphs, and show that they possess large algebraic connectivity of optimal order, provided they are not sparse (cf. Section IV). Overall, we propose a computationally efficient approach to designing fast and resilient consensus topologies by minimizing Laplacian energy.

It has been proved in [16] that $E(\mathbb{G})=\sum_{i=1}^{n}(d_{i}^{2}+d_{i})$, where $d_{i}$ denotes the degree of vertex $i$. It immediately implies that the Laplacian energy of a simple graph will increase after adding any additional edge. Thus, the Laplacian energy of an $n$-vertex graph achieves its maximum value, $n^{2}(n-1)$, when the graph is complete. Various upper and lower bounds on $E(\mathbb{G})$ have been established [21]. There has been an effort in the literature to identify optimal topologies that minimize the Laplacian energy for certain types of graphs. For example, among all $n$-vertex connected graphs, the Laplacian energy achieves its minimum value when the graph is the path [16]. Another example is that among all connected graphs with chromatic number $\chi$, the Laplacian energy achieves its minimum value, $\chi^{2}(\chi-1)$, by the $\chi$-vertex complete graph [22]. Notwithstanding these results, the following question has never been studied: Given a fixed number of vertices and edges, what are the optimal graphs that achieve minimal Laplacian energy?

This section solves the above open problem. To state our main results, we use $\lfloor\cdot\rfloor$ to denote the floor function.

The theorem states that the sequence of vertex degrees, arranged in descending order, follows the following pattern:

$$(d_{1},\ldots,d_{n})=(\;\underbrace{k+1,\ldots,k+1}_{2m-nk},\underbrace{k,\ldots,k}_{n(k+1)-2m})$$

(1)

In the special case when $\frac{2m}{n}$ is an integer, all $n$ vertices are of degree $k=\frac{2m}{n}$. Thus, Theorem 1 implies that minimal Laplacian energy graphs have an (almost) uniform degree distribution, which is intuitive from the fact that $E(\mathbb{G})=\sum_{i=1}^{n}(d_{i}^{2}+d_{i})=\sum_{i=1}^{n}d_{i}^{2}+2m$. Such a graph, whose degree difference is at most 1, is called almost regular graph. Such a graph, in which the degree difference is at most 1, is called an almost regular graph [23].

It is easy to check that the total degree sum of a minimal Laplacian energy graph specified by Theorem 1 equals $k(n(k+1)-2m)+(k+1)(2m-nk)=2m$, which is consistent with the assumption of $m$ edges. Moreover, it can be proved that such a degree distribution always admits a graph using the Erdős-Gallai theorem [24, 25].

To prove Theorem 1, we need the following results.

Proof of Theorem 1: From Lemma 1, $E(\mathbb{G})=\sum_{i=1}^{n}(d_{i}^{2}+d_{i})$. Since $\sum_{i=1}^{n}d_{i}=2m$, minimizing $E(\mathbb{G})$ is equivalent to minimizing $\sum_{i=1}^{n}d_{i}^{2}$. Without loss of generality, assume that $d_{1}\geq d_{2}\geq\cdots\geq d_{n}$.

We first minimize $\sum_{i=1}^{n}d_{i}^{2}$ without considering the constraint that $d_{1},\ldots,d_{n}$ form the degree sequence of a simple graph. Since all $d_{i}$ are integers and their summation $\sum_{i=1}^{n}d_{i}$ is a fixed constant, it is easy to see that $\sum_{i=1}^{n}d_{i}^{2}$ is minimized by the unique sequence pattern given in (1), in which $k$ and $2m-nk$ are respectively the unique quotient and remainder of $2m$ divided by $n$. With such a degree sequence, $E(\mathbb{G})=\sum_{i=1}^{n}d_{i}^{2}+2m=(k+1)^{2}(2m-nk)+k^{2}(n(k+1)-2m)+2m=(k+1)(4m-nk)$.

To prove the theorem, it is now sufficient to show that, given a fixed number of vertices $n$ and edges $m$, there exists a graph with the degree sequence specified in (1). From Lemma 2, it is equivalent to show that (I) $\sum_{i=1}^{n}d_{i}$ is even and (II) $\sum_{i=1}^{j}d_{i}\leq j(j-1)+\sum_{i=j+1}^{n}\min\{j,d_{i}\}$ for all $j\in\{1,\ldots,n\}$. First note that $\sum_{i=1}^{n}d_{i}=k(n(k+1)-2m)+(k+1)(2m-nk)=2m$, which implies that condition (I) holds. Next we will validate condition (II).

Since $k=\lfloor\frac{2m}{n}\rfloor$ and $m\leq\frac{1}{2}n(n-1)$, it follows that $k\leq n-1$. In the case when $k=n-1$, it must be true that $m=\frac{1}{2}n(n-1)$, and thus $\mathbb{G}$ is a complete graph with all $d_{i}=n-1$, which satisfies (1). Therefore, we only need to consider $k<n-1$ from here on. To validate condition (II) for all $j\in\{1,\ldots,n\}$, we consider $j\leq k$ and $j>k$ separately. First, in the case when $j\leq k$, since $d_{i}\geq k$, $j\leq d_{i}$ for all $i$. Then, $j(j-1)+\sum_{i=j+1}^{n}\min\{j,d_{i}\}=j(j-1)+(n-j)j=(n-1)j$. Meanwhile, since $d_{i}\leq k+1$ for all $i$, $\sum_{i=1}^{j}d_{i}\leq(k+1)j$. Since $k<n-1$, it follows that $\sum_{i=1}^{j}d_{i}\leq(k+1)j\leq(n-1)j=j(j-1)+\sum_{i=j+1}^{n}\min\{j,d_{i}\}$. Thus, condition (II) holds for all $j\leq k$.

Next, we consider the case when $j>k$. Since $d_{i}\leq k+1$, $j\geq d_{i}$ for all $i$, $j(j-1)+\sum_{i=j+1}^{n}\min\{j,d_{i}\}=j(j-1)+\sum_{i=j+1}^{n}d_{i}=j(j-1)+2m-\sum_{i=1}^{j}d_{i}$, in which we used $\sum_{i=1}^{n}d_{i}=2m$ in the last equality. Then, in this case condition (II) is equivalent to

$$2\sum_{i=1}^{j}d_{i}\leq j(j-1)+2m.$$

(2)

Recalling the degree sequence given in (1), we will now consider the following two cases.

Case 1: $j\leq 2m-nk$. From (1), $\sum_{i=1}^{j}d_{i}=(k+1)j$. Then, inequality (2) is equivalent to $j^{2}-(2k+3)j+2m\geq 0$. Let $f(x)=x^{2}-(2k+3)x+2m$, which is a quadratic function of $x$ and achieves its minimum at $x=k+\frac{3}{2}$. Since $j$ is an integer in the interval $[k+1,2m-nk]$, the function $f(j)=j^{2}-(2k+3)j+2m$ achieves its minimum at $j=k+1$, whose value is $f(k+1)=(k+1)^{2}-(2k+3)(k+1)+2m=2m-(k^{2}+3k+2)$. Since $2m-nk\geq k+1$ and $k<n-1$, $2m\geq(n+1)k+1\geq(k+3)k+1$. Since $2m$ is even and $(k+3)k+1$ must be odd, $2m\geq(k+3)k+2$, which implies that $f(k+1)\geq 0$. Therefore, (2) holds in this case.

Case 2: $j>2m-nk$. From (1), $\sum_{i=1}^{j}d_{i}=(k+1)(2m-nk)+k(j-2m+nk)=2m-nk-kj$. Then, inequality (2) is equivalent to $j^{2}-(2k+1)j+2nk-2m\geq 0$. Let $f(x)=x^{2}-(2k+1)x+2nk-2m$, which is a quadratic function of $x$ and achieves its minimum at $x=k+\frac{1}{2}$. Recall that $j>k$ is under consideration. Then, $j$ is an integer in the interval $[\max\{k+1,2m-nk+1\},n]$. We will consider two scenarios, $k>2m-nk$ and $k\leq 2m-nk$, separately.

First assume $k>2m-nk$, which is equivalent to $k>\frac{2m}{n+1}$. Then, $j$ is an integer in the interval $[k+1,n]$, and thus the function $f(j)=j^{2}-(2k+1)j+2nk-2m$ over this interval achieves its minimum at $f(k+1)=-k^{2}+(2n-1)k-2m$. Treat this expression as a quadratic function of $k$ which achieves its maximum at $k=n-\frac{1}{2}$. Since $k$ is an integer in the interval $(\frac{2m}{n+1},n-1)$, the function over this interval satisfies $f(k+1)>f(\frac{2m}{n+1}+1)=\frac{2m}{(n+1)^{2}}[n(n-1)-2-2m]$. Since $k<n-1$, implying $n(n-1)>2m$, and both $n(n-1)$ and $2m$ are even, $n(n-1)-2\geq 2m$. Therefore, $f(k+1)>0$, and thus (2) holds in this scenario.

Next assume $k\leq 2m-nk$, which is equivalent to $k\leq\frac{2m}{n+1}$. Then, $j$ is an integer in the interval $[2m-nk+1,n]$, and thus the function $f(j)=j^{2}-(2k+1)j+2nk-2m$ over this interval achieves its minimum at $f(2m-nk+1)=n(n+2)k^{2}-(4mn+4m-n+2)k+4m^{2}$. Note that if $k=0$, this minimum value equals $4m^{2}\geq 0$, and thus (2) holds. Hence, in the remainder of the proof, we need only consider $k\geq 1$. Also note that with $k\geq 1$, if $n=2$, for which $m$ may equal 0 or 1, this minimum value is always positive, and thus (2) holds. Hence, we also need only consider $n\geq 3$ in the remainder of the proof. Treat this expression as a quadratic function of $k$ which, without any restriction on $k$, achieves its minimum value of $-16m^{2}+(8n^{2}-8n-16)m-(n-2)^{2}$ when $k=\frac{4mn+4m-n+2}{2n(n+2)}$. But it has been assumed that $k\leq\frac{2m}{n+1}$. This minimum value is achievable only if $\frac{4mn+4m-n+2}{2n(n+2)}\leq\frac{2m}{n+1}$, which is equivalent to $m\leq\frac{1}{4}(n^{2}-n-2)$. Also treat this minimum value as a quadratic function of $m$ which achieves its maximum at $m=\frac{1}{4}(n^{2}-n-2)$. Since $k=\lfloor\frac{2m}{n}\rfloor\geq 1$, it follows that $m\geq\frac{n}{2}$. Then, the quadratic function of $m$, $g(m)=-16m^{2}+(8n^{2}-8n-16)m-(n-2)^{2}$ over the interval $[\frac{n}{2},\frac{1}{4}(n^{2}-n-2)]$ is always no smaller than $g(\frac{n}{2})=4n^{3}-9n^{2}-4n-4$, which can be straightforwardly verified to be greater than 0 for all $n\geq 3$. This implies that (2) holds. On the other hand, if $\frac{4mn+4m-n+2}{2n(n+2)}>\frac{2m}{n+1}$, which is equivalent to $m>\frac{1}{4}(n^{2}-n-2)$. Then, the quadratic function of $k$, $f(2m-nk+1)=n(n+2)k^{2}-(4mn+4m-n+2)k+4m^{2}$ over the interval $[1,\frac{2m}{n+1}]$, achieves its minimum when $k=\frac{2m}{n+1}$, with the corresponding minimum value being $\frac{2m}{(n+1)^{2})}[n(n-1)-2-2m]$, which was proven to be positive at the end of the last paragraph. Therefore, (2) always holds in this scenario.  

Theorem 1 provides a simple graphical condition, dependent solely on the degree distribution, that characterizes minimal Laplacian energy graphs. The following example shows that such a degree distribution condition does not guarantee connectivity. Consider all simple graphs with 6 vertices and 6 edges (i.e., $n=m=6$), Theorem 1 identifies three minimal Laplacian energy graphs, as illustrated in Figure 5.

In many network applications, such as distributed control and optimization [6, 26], connected graphs are often desired. The following theorem states that a connected optimal graph with the same minimal Laplacian energy always exists.

Proof of Theorem 2: In light of Theorem 1, it is sufficient to show that there exists a connected graph whose degree sequence satisfies (1). Such a graph must indeed exist, as it follows directly from Theorem 3.  

The above theorem implicitly assumes that $m\geq n-1$, otherwise there is no such connected graph. In a special case when $m=n-1$, all connected graphs are trees. It is not hard to see that the following result is a direct consequence of Theorem 2.

For general pairs of $n$ and $m$ with $m>n-1$, the optimal connected graph may not be unique. For example, for the case when $n=6$ and $m=8$, two connected minimal Laplacian energy graphs are illustrated in Figure 6.

We next present the following algorithm, which provides a procedure to construct a minimal Laplacian energy graph that is connected and satisfies the degree distribution specified by Theorem 2.

Algorithm 1: Given $n$ and $m$ with $m\geq n-1>0$, without loss of generality, label $n$ vertices from 1 to $n$. Set $k=\lfloor\frac{2m}{n}\rfloor$, which implies that $nk\leq 2m<n(k+1)$.

1. (1)

   If $n$ is even and $2m=nk$, for each $i\in\{1,\ldots,n\}$, connect vertex $i$ with each of those vertices whose indices are $(i+j)\bmod n$, $j\in\{\pm 1,\ldots,\pm\frac{k-1}{2},\frac{n}{2}\}$.

2. (2)

   If $n$ is even and $2m=nk+l$ where $l\in[1,n)$ is an even integer, first construct the graph as done in Case 2 (1), and then for each $i\in\{1,\ldots,\frac{l}{2}\}$, connect vertex $i$ and vertex $i+\frac{n-2}{2}$.

3. (3)

   If $n$ is odd and $2m=nk+1$, first for each $i\in\{1,\ldots,n\}$, connect vertex $i$ with each of those vertices whose indices are $(i+j)\bmod n$, $j\in\{\pm 1,\ldots,\pm\frac{k-1}{2}\}$, and then for each $i\in\{1,\ldots,\frac{n+1}{2}\}$, connect vertex $i$ and vertex $i+\frac{n-1}{2}$.

4. (4)

   If $n$ is odd and $2m=nk+1+l$ where $l\in[1,n-1)$ is an even integer, first construct the graph as done in Case 2 (3), and then for each $i\in\{\frac{n+3}{2},\ldots,\frac{n+1+l}{2}\}$, connect vertex $i$ and vertex $(i+\frac{n-1}{2})\bmod n$.

Proof of Theorem 3: First of all, any graph generated by Algorithm 1 must be connected, as each case within the algorithm contains a cycle with a vertex sequence $(1,2,\ldots,n,1)$. Next, it is straightforward to verify that the graphs generated by each case of the algorithm satisfy the degree sequence specified by (1).  

It can be straightforwardly checked that in the case when $n=m=6$, Algorithm 1 will follow Case 1 (1) and construct the 6-vertex path, which is consistent with Corollary 1. We further present six tailored examples, each corresponding to a distinct case outlined in Algorithm 1, as depicted in Figures 7 to 9. These examples collectively validate Theorem 3.

The graphs generated by Algorithm 1 exhibit “optimal” connectivity properties. To see this, we introduce two well-known connectivity concepts in graph theory: vertex connectivity, denoted as $v(\mathbb{G})$, which is defined as the minimum number of vertices whose removal would disconnect graph $\mathbb{G}$, and edge connectivity, denoted as $e(\mathbb{G})$, which is defined as the minimum number of edges whose removal would disconnect graph $\mathbb{G}$. For the complete graph with $n$ vertices, it is obvious that its edge connectivity equals $n-1$. However, there is no subset of vertices whose removal disconnects the complete graph. It is conventional to set its vertex connectivity as $n-1$ [27, page 149].

The theorem implies that the graphs constructed by Algorithm 1 always have the maximum vertex and edge connectivity. To see this, consider any graph $\mathbb{G}$ with $n$ vertices and $m$ edges. Its minimum degree $\delta(\mathbb{G})$ is at most $\lfloor\frac{2m}{n}\rfloor$. Since $e(\mathbb{G})\leq\delta(\mathbb{G})$ by definition and $v(\mathbb{G})\leq e(\mathbb{G})$ [28, Theorem 5], it follows that $v(\mathbb{G})\leq e(\mathbb{G})\leq\delta(\mathbb{G})\leq\lfloor\frac{2m}{n}\rfloor$.

Recall that all graphs generated by Algorithm 1 are almost regular graphs with the degree sequence specified in (1). In general, almost regular graphs do not necessarily have $v(\mathbb{G})=e(\mathbb{G})=\lfloor\frac{2m}{n}\rfloor$. To see this, consider two examples in Figure 10. The left almost regular graph has $n=6$ vertices and $m=10$ edges, but its vertex connectivity is 2 (by removing vertex 2 and vertex 5), which is smaller than $\lfloor\frac{2m}{n}\rfloor=3$. The right almost regular graph has $n=6$ vertices and $m=7$ edges, but its vertex connectivity is 1 (by removing vertex 6), so is its edge connectivity (by removing the edge between vertex 5 and vertex 6), both being smaller than $\lfloor\frac{2m}{n}\rfloor=2$.

To prove Theorem 4, we need the following notation and lemma. Let ${\cal U}$ be a vertex subset of graph $\mathbb{G}$. We use $\mathbb{G}\setminus{\cal U}$ to denote the graph resulting from removing all vertices in ${\cal U}$, along with the edges connecting any vertex in ${\cal U}$, from $\mathbb{G}$.

Proof of Lemma 3: We explicitly construct a such path between $u$ and $v$. Consider a sequence of vertex indices: $u_{0}=u$ and for any $i\geq 1$,

• •

  If $u_{i}<v-p$, define $u_{i+1}$ to be the largest index in $[u_{i}+1,u_{i}+p]$ such that vertex $u_{i+1}$ is not in ${\cal U}$. Such $u_{i+1}$ always exists because there are no $p$ vertices in ${\cal U}$ whose indices are consecutive integers in $(u,v)$.

• •

  Otherwise, the sequence ends.

By construction, vertices $u_{i}$ and $u_{i+1}$ are adjacent. Let $u_{j}$ be the final term of this sequence. Then $v-p\leq u_{j}\leq v$.

• •

  If $u_{j}=v$, we have found the path $u=u_{0}\to u_{1}\to\dots\to u_{j}=v$.

• •

  Otherwise, vertex $u_{j}$ is adjacent to $v$, so we have found the path $u=u_{0}\to u_{1}\to\dots\to u_{j}\to v$.

Either way, there is a path between $u$ and $v$.  

Proof of Theorem 4: From the preceding discussion, $v(\mathbb{G})\leq e(\mathbb{G})\leq k=\lfloor\frac{2m}{n}\rfloor$. Thus, to prove the theorem, it is sufficient to show $v(\mathbb{G})\geq k$.

Graphs constructed in Case 1 (2) are formed by adding edges to graphs in Case 1 (1); graphs constructed in Case 2 (2) are formed by adding edges to graphs in Case 2 (1); graphs constructed in Case 2 (4) are formed by adding edges to graphs in Case 2 (3). Since vertex connectivity is non-decreasing when we add edges, it suffices to check $v(\mathbb{G})\geq k$ for graphs from Case 1 (1), Case 2 (1), and Case 2 (3) only.

To prove $v(\mathbb{G})\geq k$, we will equivalently show that for any subset ${\cal U}$ of $k-1$ vertices, $\mathbb{G}\setminus{\cal U}$ is connected. Say that a vertex is deleted if it is in ${\cal U}$. Let $u,v$ be two arbitrary non-deleted vertices, where $u<v$. It suffices to show that there is a path between $u$ and $v$ in $\mathbb{G}\setminus{\cal U}$.

Case 1 (1): From the algorithm description, there is an edge between any two vertices whose indices differ by at most $k/2$. Since $k-1$ vertices are deleted, we have either

• •

  There are no $k/2$ deleted vertices whose indices are consecutive integers in $(u,v)$.

• •

  Or there are no $k/2$ deleted vertices whose indices are consecutive integers in $\{1,\dots,u-1\}\cup\{v+1,\dots,n\}$.

In either scenario, Lemma 3 implies that there is a path between $u$ and $v$ in $\mathbb{G}\setminus{\cal U}$.

Case 2 (1): From the algorithm description, there is an edge between any two vertices whose indices differ by at most $(k-1)/2$ and an edge between any vertex $i$ and vertex $i+n/2$. If either

• •

  There are no $(k-1)/2$ deleted vertices whose indices are consecutive integers in $(u,v)$.

• •

  Or there are no $(k-1)/2$ deleted vertices whose indices are consecutive integers in $\{1,\dots,u-1\}\cup\{v+1,\dots,n\}$.

then Lemma 3 implies that there is a path between $u$ and $v$ in $\mathbb{G}\setminus{\cal U}$.

Thus, it remains to consider the case in which there are $(k-1)/2$ deleted vertices whose indices are consecutive integers in $(u,v)$ and $(k-1)/2$ deleted vertices whose indices are consecutive integers in $\{1,\dots,u-1\}\cup\{v+1,\dots,n\}$. Let the former set of vertex indices be ${\cal A}$ and the latter be ${\cal B}$. Since $|{\cal U}|=k-1$, we see that ${\cal U}={\cal A}\cup{\cal B}$. Let ${\cal B}=\{b,\dots,b+(k-3)/2\}$, where indices are taken mod $n$.

If $v=u+n/2$, we directly obtain the path $u\to v$, which is what we wanted to show. Thus, suppose $v\neq u+n/2$. We will only consider the case $v<u+n/2$ because the case $v>u+n/2$ is symmetric.

Since ${\cal A}\subseteq(u,v)$, we have $v-u>(k-1)/2$, so $(v+n/2)-(u+n/2)>(k-1)/2$. Then the length of the interval $(u+n/2,v+n/2)$ is greater than $|{\cal B}|$.

• •

  If $b>u+n/2$, then ${\cal B}$ does not contain $u+n/2$, so consider the path $u\to u+n/2\to u+n/2-1\to\dots\to v$. See the left illustration in Figure 11 for this case.

• •

  Otherwise, $b\leq u+n/2$. Since the length of the interval $(u+n/2,v+n/2)$ is greater than $|{\cal B}|$, we see that ${\cal B}$ does not contain $v+n/2$. Consider the path $u\to u-1\to\dots\to v+n/2+1\to v+n/2\to v$. See the right illustration in Figure 11 for this case.

In both scenarios, we found a path between $u$ and $v$ in $\mathbb{G}\setminus{\cal U}$.

Case 2 (3): From the algorithm description, there is an edge between any two vertices whose indices differ by at most $(k-1)/2$ and an edge between $i$ and $i+(n-1)/2$ for any $1\leq i\leq\frac{n+1}{2}$.

Using the same argument as in Case 2 (1), Lemma 3 solves all scenarios, except the one where there are $(k-1)/2$ deleted vertices whose indices are consecutive integers in $(u,v)$ and $(k-1)/2$ deleted vertices whose indices are consecutive integers in $\{1,\dots,u-1\}\cup\{v+1,\dots,n\}$. Let the former set of vertex indices be ${\cal A}$ and the latter be ${\cal B}$. Since $|{\cal U}|=k-1$, we see that ${\cal U}={\cal A}\cup{\cal B}$. Let ${\cal B}=\{b,\dots,b+(k-3)/2\}$, where indices are taken mod $n$.

The condition that there is an edge between $i$ and $i+(n-1)/2$ for any $1\leq i\leq\frac{n+1}{2}$ translates to:

• •

  Vertices with index at most $(n-1)/2$ are adjacent to $i+(n-1)/2$

• •

  Vertices with index at least $(n+3)/2$ are adjacent to $i+(n+1)/2$

• •

  Vertex $(n+1)/2$ is adjacent to both $(n+1)/2+(n-1)/2$ and $(n+1)/2+(n+1)/2$.

Let $u$ be adjacent to $u+(n+\varepsilon_{u})/2$, and $v$ be adjacent to $v+(n+\varepsilon_{v})/2$, where $\varepsilon_{u},\varepsilon_{v}\in\{-1,1\}$. We claim that the length of the interval $(u+(n+\varepsilon_{u})/2,v+(n+\varepsilon_{u})/2)$ is greater than $(k-1)/2$.

Since ${\cal A}\subseteq(u,v)$, we have $v-u\geq(k+1)/2$, so the length of the interval is at least $(k-1)/2$. For the length to equal $(k-1)/2$, vertex $u$ must be adjacent to $u+(n+1)/2$, and vertex $v$ must be adjacent to $v+(n-1)/2$. If $u,v\neq(n+1)/2$, we immediately reach a contradiction because $u<v$. If $u=(n+1)/2$, change $\varepsilon_{u}$ to $-1$. If $v$ equals $(n+1)/2$, change $\varepsilon_{v}$ to $1$. Thus, we can always ensure that the length of the interval is greater than $(k-1)/2$.

• •

  If $b>u+(n+\varepsilon_{u})/2$, then ${\cal B}$ does not contain $u+(n+\varepsilon_{u})/2$, so consider the path $u\to u+(n+\varepsilon_{u})/2\to u+(n+\varepsilon_{u})/2-1\to\dots\to v$.

• •

  Otherwise, $b<u+(n+\varepsilon_{u})/2$. Since the length of the interval $(u+(n+\varepsilon_{u})/2,v+(n+\varepsilon_{u})/2)$ is greater than $|{\cal B}|$, we see that ${\cal B}$ does not contain $v+(n+\varepsilon_{v})/2$, so consider the path $u\to u-1\to\dots\to v+(n+\varepsilon_{v})/2+1\to v+(n+\varepsilon_{v})/2\to v$.

In both scenarios, we found a path between $u$ and $v$ in $\mathbb{G}\setminus{\cal U}$.

In all cases, we have found a path between any two vertices in $\mathbb{G}\setminus{\cal U}$, so $\mathbb{G}\setminus{\cal U}$ is connected. Thus, $v(\mathbb{G})=k$, which completes the proof.  

In this section, we study the algebraic connectivity of the minimal Laplacian energy graphs generated by Algorithm 1. We will show that the generated “dense” graphs possess large algebraic connectivity, while the generated “sparse” graphs do not. This finding is consistent with the observations from the figures in the introduction.

Among all non-complete graphs with $n$ vertices and $m$ edges, it is known that $a(\mathbb{G})\leq v(\mathbb{G})$ [9, Theorem 4.1]. From the preceding discussion, it follows that $a(\mathbb{G})\leq\lfloor\frac{2m}{n}\rfloor$ for all non-complete graphs. Theorem 5 gives a lower bound on algebraic connectivity of graphs constructed by Algorithm 1.

Note that $\bar{k}\leq k+1\leq\frac{2m}{n}+1\leq n$. We will use this fact without special mention in the sequel.

To prove Theorem 5, we need the following concept and results. A circulant matrix is a square matrix in which all rows are composed of the same entries and each row is rotated one entry to the right relative to the preceding row. The spectrum of any circulant matrix can be completely determined by its first row entries, as specified in the following lemma:

Proof of Lemma 5: From the angle addition and subtraction formulae, $2\cos a\sin b=\sin(a+b)-\sin(a-b)$ for any $a,b\in{\rm I\!R}$. Let $a=2pi\pi/n$ and $b=i\pi/n$. Since $\sin(i\pi/n)>0$ for all integers $i\in\{1,2,\ldots,n-1\}$, it follows that for all integers $i\in\{1,2,\ldots,n-1\}$,

$$2\cos\bigg{(}\frac{2pi\pi}{n}\bigg{)}=\frac{\sin((2p+1)i\pi/n)-\sin((2p-1)i\pi/n)}{\sin(i\pi/n)}.$$

Summing this relation over index $p$ from $1$ to $\lfloor\frac{k}{2}\rfloor$,

$$2\sum_{p=1}^{\lfloor\frac{k}{2}\rfloor}\cos\bigg{(}\frac{2pi\pi}{n}\bigg{)}=\frac{\sin(\bar{k}i\pi/n)}{\sin(i\pi/n)}-1.$$

It remains to identify the optimal integers $i$ over the interval $[1,n-1]$ that maximize $\frac{\sin(\bar{k}i\pi/n)}{\sin(i\pi/n)}$. To this end, define a function $f(x)=\frac{\sin(\bar{k}x)}{\sin(x)}$. Figure 12 provides an example plot. First, we check that $f(x)$ is symmetric around $\pi/2$. Since $\bar{k}=2\lfloor k/2\rfloor+1$ is odd,

$$f(\pi-x)=\frac{\sin(\bar{k}(\pi-x))}{\sin(\pi-x)}=\frac{\sin(\pi-\bar{k}x)}{\sin(\pi-x)}=\frac{\sin(\bar{k}x)}{\sin(x)}=f(x).$$

Thus, it suffices to show $f(\pi/n)\geq f(i\pi/n)$ for all integers $i\in(0,n/2]$. Second, we show that in the interval $(0,\pi)$, $f(x)$ attains its maximum of $\bar{k}$ as $x$ approaches $0$ or $\pi$. Clearly, $\lim_{x\to 0}f(x)=\lim_{x\to\pi}f(x)=\bar{k}$. Meanwhile,

	$\displaystyle|f(x)|$	$\displaystyle=\bigg{|}\frac{e^{j\bar{k}x}-e^{-j\bar{k}x}}{e^{jx}-e^{-jx}}\bigg{|}$
		$\displaystyle=\big{|}e^{j(\bar{k}-1)x}+e^{j(\bar{k}-3)x}+\dots+e^{j(-\bar{k}+1)x}\big{|}$
		$\displaystyle\leq\big{|}e^{j(\bar{k}-1)x}\big{|}+\big{|}e^{j(\bar{k}-3)x}\big{|}+\dots+\big{|}e^{j(-\bar{k}+1)x}\big{|}\leq\bar{k}.$

Finally, observe that $f(x)$ has roots at $\pi/\bar{k},2\pi/\bar{k},\dots,(\bar{k}-1)\pi/\bar{k}$ and has a maximum/minimum in each interval $(p\pi/\bar{k},(p+1)\pi/\bar{k})$, where $0\leq p\leq\bar{k}-1$. Since $k\leq n-2$ by assumption, we have $\bar{k}\leq n-1$, so $\pi/n$ is always in the leftmost interval and is closest to $x$-coordinate of the global maximum at 0. Hence, $f(\pi/n)\geq f(i\pi/n)$ for all integers $i\in(0,n/2]$.