# Algebraic Connectivity and Disjoint Vertex Subsets of Graphs

Authors: Yan Sun; Faxu Li
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

It is well known that the algebraic connectivity of a graph is the second small eigenvalue of its Laplacian matrix. In this paper, we mainly research the relationships between the algebraic connectivity and the disjoint vertex subsets of graphs, which are presented through some upper bounds on algebraic connectivity.


---

## Body

## 1. Introduction

A graphG is often used to model a complex network. The vertex set and the edge set of graph G are denoted by N and ℰ, respectively. A network is represented as an undirected graph G=N,ℰ consisting of N=N nodes and E=ℰ links, respectively.Graph theory has provided chemists with a variety of useful tools, such as in the topological structure [1–3]. The Laplacian matrix of a graph G is denoted by L, and L=D−A, where D is a diagonal matrix whose diagonal entries are its degrees and A is the adjacency matrix of G. The Laplacian eigenvalues of a graph G are the eigenvalues of L, denoted by 0=μN≤μN−1≤…≤μ1, which are all real and nonnegative. The second smallest Laplacian eigenvalue μN−1 of a graph is well known as the algebraic connectivity, which was first studied by Fiedler [4]. The algebraic connectivity [5] of a graph is important for the connectivity of a graph [6], which can be used to measure the robustness of a graph. It has been emerged as an important parameter in many system problems [7–18]. Especially, the algebraic connectivity also plays an important role in the partitions of a complex network. For the literature on the algebraic connectivity of a graph [19], the reader is referred to [20, 21]. In this work, the relationships are researched between the algebraic connectivity and disjoint vertex subsets of graphs, which are presented through some upper bounds.


## 2. Preliminaries

Letx∈Rn be a vector. Let B be an incidence matrix of G. Then, xTLx=BTx22=∑i,j∈Εxi−xj2. For any vector x,y∈Rn, the inner product of x and y is defined as x,y. Two upper bounds on the algebraic connectivity are given as follows.Lemma 1 (see [20]).
For any vectorf∈Rn, the Rayleigh inequality is as follows:(1)μN−1≤Lf,ff,f,where f,c=0, c is a constant, and Lf,f=∑vi,vj∈Εfvi−fvj2, fvi is the vector f for the node vi.Lemma 2 (see [20]).
For any vectorf∈Rn, we have(2)μN−1≤∑vivj∈Εfvi−fvj2∑vi∈Nf2vi,(3)μN−1≤∑vi,vj∈ℰfvi−fvj2∑vi∈N∑vj∈Nfvi−fvj2,where fvi is the vector f for the node vi.LetA and B be two disjoint subsets of N, respectively. The distance between two disjoint subsets A and B of N is denoted by hA,B. For continence, h takes the place of hA,B. Let hu,A be the distance between the node u and A, which is the shortest distance of the node u∈N to a node of the set A. Suppose a=A/N and b=B/N. A result on the algebraic connectivity and two partitions of graphs is presented by Alon [22] and Milman [20] below.Lemma 3 (see [23]).
For any two disjoint subsetsA and B of N, it holds(4)μN−1≤1Nh21a+1bE−EA−EB,where EA and EB are the number of links in the sets A and B, respectively.Moreover, the next step consider the case of three disjoint vertex subsets of graphs [24].


## 3. Main Result

LetA, B, and C be the subsets of N, respectively, where their numbers of nodes are, respectively, A, B, and C. Assume a=A/N,b=B/N,andc=C/N. Let hu,A,hu,B,andhu,C be the distances from the node u∈N to subsets A,B,andC of N, respectively. Suppose hs=minhA,B,hA,C,hB,C. Now, we construct a function gu related to node u as follows, where the constructed function is referred to the book [25]:(5)gu=131a+1b+1c−191a+1b+1c×minhs,hu,A,hu,B,hu,Chs.Letf=g−g¯≠0, where g¯=1/N∑n∈Ngn. It is easy to check that f,c=0, where c is a constant function [26–30]. Meanwhile, g,c≠0 can be checked. Thus, the following cases need to discussed.Case 1.
If the nodeu belongs to any one subset of A,B,C, then(6)0=minhs,hu,A,hu,B,hu,C,(7)gu=131a+1b+1c>0.Case 2.
If the nodeu∈N−A,B,C, then we can see that(8)minhs,hu,A,hu,B,hu,Chs≤1,(9)gu=131a+1b+1c−191a+1b+1c×minhs,hu,A,hu,B,hu,Chs>0.
By Case1 and Case 2, g,c≠0 holds. In contrast, if g,c=0, then gu=0 for each u∈N and g−g¯=0, which is a contradiction with f=g−g¯≠0. From the definition gu, for any two adjacent nodes uandv, we have(10)gu−gv≤19hs1a+1b+1c.
Our main result is as follows.Theorem 1.
LetA,B,andC∈N be three disjoint subsets of N. Let EA and EB and EC be the numbers of links in the sets A and B and C, respectively. Then,(11)μN−1≤181N2hs21a+1b+1cE−EA−EB−EC=181Nhs21NA+1NB+1NCE−EA−EB−EC.Proof.
For subsetsA,B, and C, by Lemma 2, we have(12)∑u,v∈εfu−fv2=∑u,v∈εgu−gv2=∑u,v∈ε−A∪B∪Cgu−gv2≤181hs21a+1b+1c2E−EA−EB−EC.
From (2) and(13)g¯=1N∑n∈Ngn,∑n∈Nf2n≥∑n∈A∪B∪Cgn−g¯2,where g¯=0, and since the coordinates of the center of gravity of the three regions are the average of the triangle region, then the vectors gu,A+gu,B+gu,C=0. The sum of the vectors of the center of gravity of the triangle to the vertices is equal to 0 [25]. The center of gravity is analogous to the mean or average from statistics [6, 31, 32]:(14)∑n∈Nf2n≥∑n∈A∪B∪Cf2n=∑n∈Agn−g¯2+∑n∈Bgn−g¯2+∑n∈Cgn−g¯2=A131a+1b+1c−g¯2+B131a+1b+1c−g¯2+C131a+1b+1c−g¯2=A131a+1b+1c2+B131a+1b+1c2+C131a+1b+1c2=A+B+C131a+1b+1c2=19A1a+B1b+C1c21a+1b+1c=N2191+1+121a+1b+1c≥N21a+1b+1c.
By the above inequalities and Lemma2, it arrives that(15)μN−1≤181N2hs21a+1b+1cE−EA−EB−EC=181Nhs21NC+1NB+1NCE−EA−EB−EC.Example 1.
Figure1 describes the graphs G1 and G2, each with N=7 nodes, L=10 links, and a diameter ρ=4. For G1 subsets, A=v1v3v5v6v7,B=v2,andC=v4. For G2 subsets, A=u1u2u3,B=u4,C=u5u6u7,andhs=0.5. Their algebraic connectivity [33] and their upper bounds on (11) are as follows. For the G1 and G2 aplacian matrixes,(16)G1=2−1−10000−13−10−1001−14−1−10000−13−1−100−1−1−14−10000−1−13−100000−11,G2=2−1−10000−13−10−100−1−130−1000003−1−1−10−1−1−14−10000−1−13−1000−10−12.
ForG1, the algebraic connectivity is 0.6338, and the algebraic connectivity of G2 is 0.5858. For G1 upper bounds on μN−1G1≤1/81N2hs21/a+1/b+1/cE−EA−EB−EC=0.0931.
ForG2 upper bounds on μN−1G2≤1/81N2hs21/a+1/b+1/cE−EA−EB−EC=0.0587.
A graph with the second smallest Laplacian eigenvalueμN−1 is thus more robust, in the sense of being better connected.Figure 1
The graphsG1 and G2.Proposition 1.
LetA,B,andC∈V be three disjoint subsets of V. Suppose hs=1 and D=V−A−B−C. Let mA, mB, mC, and mD be the number of links in the sets A,B,C, and D, respectively. Then,(17)μN−1≤1/811/a+1/b+1/c2m−mA−mB−mC−mDA+B+C1/a+1/b+1/c−g¯2+D2/91/a+1/b+1/c−g¯2,where(18)g¯=1n1a+1b+1cA+B+C+29D,in which g¯ is the average of the A,B,C,D field.Proof.
For subsetsA,B, and C, by Lemma 2, we have(19)∑u,v∈Εfu−fv2=∑u,v∈Εgu−gv2=∑u,v∈Ε−EA∪EB∪EC∪EDgu−gv2≤1811a+1b+1c2m−mA−mB−mC−mD,where links of the sets in the node sets A, B, C, and D are EA,EB, EC, and ED, respectively. From (2), we obtain(20)∑n∈Vf2n=∑n∈A∪B∪C∪Df2n=∑n∈Agn−g¯2+∑n∈Bgn−g¯2+∑v∈Cgn−g¯2+∑n∈Dgn−g¯2=A1a+1b+1c−g¯2+B1a+1b+1c−g¯2+C1a+1b+1c−g¯2+D291a+1b+1c−g¯2=A+B+C1a+1b+1c−g¯2+D291a+1b+1c−g¯2.
By direct computation, we have(21)g¯=1n1a+1b+1cA+B+C+29D.
By the above equalities and Lemma2, inequality (17) holds.
But, we note that the algebraic connectivity [34, 35], μN−1, should not be seen as a strict disconnection or a robustness metric [36].Example 2.
For example, Figure2 describes the graphs G3 and G4, with n=9, m=12, and diameter 6. By direct calculation, for G3 subsets, A=v1v2v3,B=v4v5v6,C=v7,andD=v8v9, and for G4 subsets, A=u1u2u3,B=u4u5u6,C=u7,andD=u8u9. Their algebraic connectivity G3 is 0.4798 and G4 is 0.4817, respectively. Their Laplacian matrices LG3 and LG4, for G3 upper bounds on μN−1G3≥0.431 and for G4 upper bounds on μN−1G4≥0.357.
Theorem1 and Proposition 1 are two completely different situations. The theorem hypothesis is that A,B,andC∈N be three disjoint subsets of N. The proposition supposes that A,B,andC∈V be three disjoint subsets of V and hs=1 and D=V−A−B−C. In other words, the proposition has constraints. Moreover, it is not the same as the four disjoint subsets of N.Figure 2
The graphsG3 and G4.



---

*Source: 5763218-2020-07-31.xml*