# Characterization of Graphs with an Eigenvalue of Large Multiplicity

Authors: Linming Qi; Lianying Miao; Weiliang Zhao; Lu Liu
Journal: Advances in Mathematical Physics
 (2020)

---

## Abstract

LetG be a simple and undirected graph. The eigenvalues of the adjacency matrix of G are called the eigenvalues of G. In this paper, we characterize all the n-vertex graphs with some eigenvalue of multiplicity n−2 and n−3, respectively. Moreover, as an application of the main result, we present a family of nonregular graphs with four distinct eigenvalues.


---

## Body

## 1. Introduction

All graphs here considered are simple, undirected, and connected. LetG be a graph with vertex set VG=v1,v2,⋯,vn. The set of all the neighbors of a vertex vi is denoted by NGvi. Two adjacent vertices vi and vj are denoted by vi~vj. The adjacency matrix AG=aij of G is a real symmetric matrix, and aij=1 if there is an edge joining the vertices vi and vj; otherwise, aij=0. The eigenvalues of AG are called the eigenvalues of G, denoted by ρ1≥ρ2≥⋯≥ρn. The rank of the adjacency matrix AG of G is called the rank of G, written as rG. The rank of a matrix M is also written as rM. An independent set of G is a subset of VG such that there is no edge between any two vertices. The number of vertices in a maximum independent set of G is called the independent number of G, denoted by μG. The distance between two vertices vi and vj, denoted by dvi,vj, is the length of a shortest path between vi and vj. Denote by diamG the diameter of G, then diamG=maxdvi,vj:vi,vj∈VG. Let mρi be the multiplicity of an eigenvalue ρi of a graph G.The multiplicity of an eigenvalue of a graph has attracted much attention. Rowlinson gives an extensive investigation in this topic [1–8]. Let G be a graph of order n with an eigenvalue ρ. In [1], the author proved that if mρ=k and ρ≠0,−1, then k≤1/2t−1t+4 with t=n−k. This upper bound was extended to k≤1/2tt−1 with t=n−k>2 (or equivalently, k≤n+1/2−2n+1/4) in [2]. The graphs satisfying k=1/2tt−1 were discussed in [5]. In [3, 4, 6–8], the authors studied the multiplicity of an eigenvalue of a graph in some special graph classes. Moreover, Fonseca [9] proved many relations between the multiplicities of an eigenvalue whenever a path is removed from the graph. Bu et al. [10] gave two upper bounds on eigenvalue multiplicity of unicyclic graphs and trees. Wong et al. [11] improved an upper bound on the multiplicity of a positive eigenvalue of a tree in [3].Notice that the upper bounds in [1, 2] are established for the multiplicity of the eigenvalue not equal to 0 or -1. In other words, the multiplicities of the eigenvalues 0 and -1 cannot be bounded easily. Then, it is interesting to study the multiplicities of the eigenvalues 0 and -1 of graphs. Here, we are interested in searching the graphs with the eigenvalue -1 or 0 of large multiplicity. It is well known that the multiplicity of the eigenvalue 0 is called the nullity of a graph, which has been studied intensively. Hence, attention may be paid to the graphs with the eigenvalue -1 of large multiplicity. More generally, in this paper, we investigate the graphs with some eigenvalue of large multiplicity because they are related to the graphs with few distinct eigenvalues, which have been investigated intensively (see [12–18], for example).Denote the set of alln-vertex connected graphs with some eigenvalue of multiplicity k by Gn,k. The following are the main conclusions of this paper.Theorem 1.
LetG be a graph of order n>3, then G∈Gn,n−2 if and only if G is the complete bipartite graph Ks,t with s+t=n.Theorem 2.
LetG be a graph of order n>6, then G∈Gn,n−3 if and only if G is the complete tripartite graph Ka,b,c with a+b+c=n or the graph Γ (see Figure 1) with s,t,p≥1 and s+t+p=n.Figure 1
The graphΓ.


## 2. Proofs

Before showing the proofs of Theorems1 and 2, we first present some known results as lemmas.Lemma 3 (interlacing theorem, [19]).
For a real symmetric matrixA of order n, let M be a principal submatrix of A with order s≤n. Then,
(1)λi+n−sA≤λiM≤λiA,1≤i≤s,where λi is the ith largest eigenvalue.LetH be a symmetric real matrix, whose block form is
(2)H=H11⋯H1t⋮⋱⋮Ht1⋯Htt,where the transpose of Hij is Hji. Let qij be the average row sum of Hij, then Q=qij is the quotient matrix of H. If the row sum of Hij is constant, then we say H has an equitable partition.Lemma 4 (see [19]).
LetH be a symmetric real matrix having an equitable partition and Q be the quotient matrix of H. Then, each eigenvalue of Q is an eigenvalue of H.Lemma 5 (see [20, 21]).
LetG be a graph, then rG=2 if and only if G is a complete bipartite graph, and rG=3 if and only if G is a complete tripartite graph.Lemma 6 (see [2]).
LetG be a graph of order n and ρ be an eigenvalue of multiplicity k. If ρ∉0,−1, then
(3)k≤n+12−2n+14,or equivalently, k≤1/2tt−1 with t=n−k>2.Lemma 7.
LetG be a graph with n vertices and K=v1,⋯,vq induces a clique in G such that NGvi−K=NGvj−K 1≤i,j≤q, then −1 is an eigenvalue of G with multiplicity at least q−1.Proof.
SinceK=v1,⋯,vq induces a clique of G and NGvi−K=NGvj−K 1≤i,j≤q, then the first q rows of the matrix AG+I are identical, where I is the identity matrix. Thus AG+I contains 0 as an eigenvalue of multiplicity at least q−1, which indicates that −1 is an eigenvalue of AG with multiplicity at least q−1.In the following, we present the proofs of Theorems1 and 2.


### 2.1. Proof of Theorem1

LetG be a graph of order n≥4. If G is the complete bipartite graph Ks,t with s+t=n, then it is easy to know that all the eigenvalues of Ks,t are st,−st,0 with multiplicities 1,1,n−2, respectively. Thus, G=Ks,t∈Gn,n−2.Now suppose thatG∈Gn,n−2. We will show that G must be a complete bipartite graph. Let θ be the eigenvalue of G with multiplicity n−2. First, assume that θ=0, then the rank rG of G is 2, and thus, G is a complete bipartite graph from Lemma 5. Next, assume that θ≠0 (this case cannot happen from the following proof). Then, rAG−θI=2 with I as the identity matrix, which indicates that the independent number μG≤2 (otherwise, rAG−θI>2 clearly, a contradiction). Moreover, we claim that G is a cograph, i.e., G contains no path P4 as an induced subgraph. Otherwise, assume that G contains P4 as an induced subgraph, and then, AP4 (resp., AP4−θI) is a principal submatrix of AG (resp., AG−θI). Thus, one can obtain that
(4)rAG−θI≥rAP4−θI≥3a contradiction. As a result, diamG≤2. If diamG=1, G is the complete graph Kn whose eigenvalues are n−1 and −1 with multiplicity 1 and n−1, respectively. Obviously, Kn∉Gn,n−2. Suppose that diamG=2 and H is an arbitrary connected subgraph with order 4 of G in the following. For the eigenvalues ρi of G and λi of H, it follows from Lemma 3 that
(5)ρ1≥λ1≥ρn−3,ρ2≥λ2≥ρn−2,ρ3≥λ3≥ρn−1,ρ4≥λ4≥ρn.SinceG∈Gn,n−2, we obtain that H also contains θ≠0 as an eigenvalue of multiplicity at least 2. Recalling that μG≤2, diamG=2, and G is a cograph, then H must be isomorphic to one of the graphs H1,H2,H3 (see Figure 2). However, by direct calculation, Hi1≤i≤3 contains no nonzero eigenvalue of multiplicity at least 2 from Table 1, a contradiction.Figure 2
The graphsH1,H2, and H3.Table 1
The eigenvalues of graphsHi1≤i≤3.
H1
-1.4812
-1
0.3111
2.1701
H2
-2
0
0
2
H3
-1.5616
-1
0
2.5616Consequently, the proof is completed.


### 2.2. Proof of Theorem2

LetG be a graph of order n>6. We first show the sufficiency part. If G is the complete tripartite graph Ka,b,c with a+b+c=n, then from Lemma 5, it is clear that Ka,b,c∈Gn,n−3 with eigenvalue 0 of multiplicity n−3. Suppose that G is the graph Γ with s,t,p≥1 and s+t+p=n in Figure 1. From Lemma 7, Γ contains −1 as an eigenvalue of multiplicity at least s+t+p−3=n−3. According to the partition VΓ=VKs,VKt,VKp, the quotient matrix Q of AΓ is
(6)Q=s−1p0sp−1t0pt−1.By calculation, the determinant of the matrixQ+I is
(7)detQ+I=−pst≠0,which implies that −1 is not an eigenvalue of the quotient matrix Q. Applying Lemma 4, we obtain that −1 is an eigenvalue of Γ with multiplicity n−3; that is, Γ∈Gn,n−3.We now prove the necessity part. Suppose thatG∈Gn,n−3 and θ is the eigenvalue of G with multiplicity n−3. First, if θ=0, then rG=3 and G is a complete tripartite graph Ka,b,c with a+b+c=n from Lemma 5. Next, suppose that θ≠0, then rAG−θI=3. We claim that the independent number μG=2. Assume on the contrary that μG≠2. If μG=1, G is the complete graph Kn and Kn∉Gn,n−3 from the proof of Theorem 1. Suppose that μG≥4 with v1,v2,v3,v4 an independent set of G, and let M be the principal submatrix of AG indexed by v1,v2,v3,v4. Then,
(8)rAG−θI≥rM−θI=4,contradicting with rAG−θI=3.Now suppose thatμG=3 with S=v1,v2,v3 a maximum independent set of G, which yields that each vertex out of S must be adjacent to at least one of S. To complete the proof, the following claims are necessary.Claim 1.
The eigenvalueθ=−1.
Recalling thatθ≠0, further, if θ≠−1, then from Lemma 6 and n>6,
(9)mθ≤n+12−2n+14<n−3,contradicting with mθ=n−3. Hence, θ=−1.Claim 2.
There exists no vertex adjacent to exactly two ofv1,v2,v3.
Without loss of generality, suppose for a contradiction that there exists a vertexu such that u~v1, u~v2 and u≁v3. Let M be the principal submatrix of AG indexed by v1,v2,v3,u, then M−θI is a principal submatrix of AG−θI and
(10)M−θI=−θ0010−θ0100−θ0110−θ.Denote byRvi the row of AG−θI indexed by the vertex vi. Since rAG−θI=3, it is clear that Rv1,Rv2,Rv3 are linearly independent, which yields that any other rows of AG−θI can be written as a linear combination of Rv1,Rv2,Rv3. Let
(11)Ru=aRv1+bRv2+cRv3.Applying (11) to the first, second, and fourth columns of M−θI, we get
(12)−aθ=1,−bθ=1,a+b=−θ,which yields that θ2=2, contradicting with Claim 1.Claim 3.
There exists no vertex adjacent to each ofv1,v2,v3.Suppose for a contradiction that there exists a vertexu such that u~vii=1,2,3. Analogous with the proof of Claim 2, let M be the principal submatrix of AG indexed by v1,v2,v3,u, then
(13)M−θI=−θ0010−θ0100−θ1111−θ.AsrAG−θI=3, then clearly Rv1,Rv2,Rv3 are linearly independent, which span the row space of AG−θI. Let
(14)Ru=aRv1+bRv2+cRv3.Applying (14) to the columns of M−θI, we get
(15)−aθ=1,−bθ=1,−cθ=1,a+b+c=−θ,which implies that θ2=3, contradicting with Claim 1. Combining the above claims, we see that if μG=3, then G is not connected, a contradiction. As a result, μG≠3. Recalling the discussions before, it can be proved that μG=2.In what follows, we prove thatG contains no induced path P4, i.e., G is a cograph. If G contains P4 as an induced subgraph, then by considering an induced subgraph of order 5 of G, we see that G must contain some Gi 1≤i≤4 (see Figure 3) as an induced subgraph (noting that μG=2). Applying Lemma 3 and Claim 1, we obtain that Gi 1≤i≤5 contains θ=−1 as an eigenvalue of multiplicity at least 2. However, by direct calculation, it follows that the multiplicity of −1 as an eigenvalue of Gi 1≤i≤5 is not more than one (see Table 2), a contradiction. Therefore, G is a cograph and the diameter diamG=2.Figure 3
The graphsGi1≤i≤5.Table 2
The eigenvalues of graphsGi1≤i≤4.
G1
-1.618
-1.618
0.618
0.618
2
G2
-1
-0.5392
-1.6751
1
2.2143
G3
-1
-0.5892
-1.7757
0.7237
2.6412
G4
-1.1701
-2
0
0.6889
2.4812
G5
-1.618
-1.4728
-0.4626
0.618
2.9354Now we are in a position to complete the proof. Note thatμG=2 and diamG=2 from the above process. Let P3=v1v2v3 be a diameter of G, then v1,v3 is a maximum independent set of G and each vertex out of v1,v3 is adjacent to at least one of v1,v3. Let
(16)Sv1=vi∈VG\VP3:vi~v1,vi≁v3,Sv2=vi∈VG\VP3:vi~v1,vi~v3,Sv3=vi∈VG\VP3:vi≁v1,vi~v3,then any vertex out of VP3 belongs precisely to one of Svi1≤i≤3. The following claims are needed for us.Claim 4.
Each vertex ofSv1 (resp., Sv3) is adjacent to each one of Sv2.Supposeu∈Sv1 and w∈Sv2 such that u≁w. Then, the vertices u,v1,w,v3 induce a path P4, a contradiction. The proof for the case of Sv3 is parallel, omitted.Claim 5.
All the vertices ofSv1 (resp., Sv3) induce a clique of G.We only prove the case ofSv1. If x,y∈Sv1 and x≁y, then x,y,v3 induce an independent set of G, contradicting with μG=2.Claim 6.
All the vertices ofSv2 induce a clique of G.Assume thatx,y∈Sv2 and x≁y. Considering an induced subgraph H of order 5 of G, we obtain that H is isomorphic to one of X1,X2,X3(see Figure 4). It follows from Lemma 3 that H contains θ as an eigenvalue of multiplicity at least 2. But Xi1≤i≤3 contains no eigenvalue of multiplicity 2 from Table 3, a contradiction.Figure 4
The graphsXi1≤i≤3.Table 3
The eigenvalues of graphsXi1≤i≤3.
X1
-2.1774
-1
0
0.3216
2.8558
X2
-2.1774
-1
0
0.3216
2.8558
X3
-2
-1.2361
0
0
3.2361From Claims4–6 and the facts μG=2 and diamG=2, we derive that G is isomorphic to the graph Γ in Figure 1, as required. The proof is completed.van Dam [14] and Huang and Huang [18] investigated the regular graphs with four distinct eigenvalues. Here, as an application of Theorem 2, we obtain a family of nonregular graphs with four distinct eigenvalues.Corollary 8.
The graphΓ with s,t,p≥1 and s+t+p=n (see Figure 1) contains four distinct eigenvalues, which is not a regular graph.Proof.
From the proof of Theorem2, we see that −1 is an eigenvalue of Γ with multiplicity n−3 and the remaining three eigenvalues of Γ are those of the quotient matrix Q of AΓ. Since detQ+I=−pst<0, then Q+I contains two positive eigenvalues and one negative eigenvalue. By the Perron-Frobenius theorem, the largest eigenvalue of Γ is simple; then, the largest eigenvalue of Q (resp., Q+I) is simple. Thus, Q+I contains three distinct eigenvalues, that is, Q contains three distinct eigenvalues. Recalling that −1 is not an eigenvalue of Q, then Γ contains four distinct eigenvalues. Moreover, it is clear that Γ is not a regular graph.


## 2.1. Proof of Theorem1

LetG be a graph of order n≥4. If G is the complete bipartite graph Ks,t with s+t=n, then it is easy to know that all the eigenvalues of Ks,t are st,−st,0 with multiplicities 1,1,n−2, respectively. Thus, G=Ks,t∈Gn,n−2.Now suppose thatG∈Gn,n−2. We will show that G must be a complete bipartite graph. Let θ be the eigenvalue of G with multiplicity n−2. First, assume that θ=0, then the rank rG of G is 2, and thus, G is a complete bipartite graph from Lemma 5. Next, assume that θ≠0 (this case cannot happen from the following proof). Then, rAG−θI=2 with I as the identity matrix, which indicates that the independent number μG≤2 (otherwise, rAG−θI>2 clearly, a contradiction). Moreover, we claim that G is a cograph, i.e., G contains no path P4 as an induced subgraph. Otherwise, assume that G contains P4 as an induced subgraph, and then, AP4 (resp., AP4−θI) is a principal submatrix of AG (resp., AG−θI). Thus, one can obtain that
(4)rAG−θI≥rAP4−θI≥3a contradiction. As a result, diamG≤2. If diamG=1, G is the complete graph Kn whose eigenvalues are n−1 and −1 with multiplicity 1 and n−1, respectively. Obviously, Kn∉Gn,n−2. Suppose that diamG=2 and H is an arbitrary connected subgraph with order 4 of G in the following. For the eigenvalues ρi of G and λi of H, it follows from Lemma 3 that
(5)ρ1≥λ1≥ρn−3,ρ2≥λ2≥ρn−2,ρ3≥λ3≥ρn−1,ρ4≥λ4≥ρn.SinceG∈Gn,n−2, we obtain that H also contains θ≠0 as an eigenvalue of multiplicity at least 2. Recalling that μG≤2, diamG=2, and G is a cograph, then H must be isomorphic to one of the graphs H1,H2,H3 (see Figure 2). However, by direct calculation, Hi1≤i≤3 contains no nonzero eigenvalue of multiplicity at least 2 from Table 1, a contradiction.Figure 2
The graphsH1,H2, and H3.Table 1
The eigenvalues of graphsHi1≤i≤3.
H1
-1.4812
-1
0.3111
2.1701
H2
-2
0
0
2
H3
-1.5616
-1
0
2.5616Consequently, the proof is completed.


## 2.2. Proof of Theorem2

LetG be a graph of order n>6. We first show the sufficiency part. If G is the complete tripartite graph Ka,b,c with a+b+c=n, then from Lemma 5, it is clear that Ka,b,c∈Gn,n−3 with eigenvalue 0 of multiplicity n−3. Suppose that G is the graph Γ with s,t,p≥1 and s+t+p=n in Figure 1. From Lemma 7, Γ contains −1 as an eigenvalue of multiplicity at least s+t+p−3=n−3. According to the partition VΓ=VKs,VKt,VKp, the quotient matrix Q of AΓ is
(6)Q=s−1p0sp−1t0pt−1.By calculation, the determinant of the matrixQ+I is
(7)detQ+I=−pst≠0,which implies that −1 is not an eigenvalue of the quotient matrix Q. Applying Lemma 4, we obtain that −1 is an eigenvalue of Γ with multiplicity n−3; that is, Γ∈Gn,n−3.We now prove the necessity part. Suppose thatG∈Gn,n−3 and θ is the eigenvalue of G with multiplicity n−3. First, if θ=0, then rG=3 and G is a complete tripartite graph Ka,b,c with a+b+c=n from Lemma 5. Next, suppose that θ≠0, then rAG−θI=3. We claim that the independent number μG=2. Assume on the contrary that μG≠2. If μG=1, G is the complete graph Kn and Kn∉Gn,n−3 from the proof of Theorem 1. Suppose that μG≥4 with v1,v2,v3,v4 an independent set of G, and let M be the principal submatrix of AG indexed by v1,v2,v3,v4. Then,
(8)rAG−θI≥rM−θI=4,contradicting with rAG−θI=3.Now suppose thatμG=3 with S=v1,v2,v3 a maximum independent set of G, which yields that each vertex out of S must be adjacent to at least one of S. To complete the proof, the following claims are necessary.Claim 1.
The eigenvalueθ=−1.
Recalling thatθ≠0, further, if θ≠−1, then from Lemma 6 and n>6,
(9)mθ≤n+12−2n+14<n−3,contradicting with mθ=n−3. Hence, θ=−1.Claim 2.
There exists no vertex adjacent to exactly two ofv1,v2,v3.
Without loss of generality, suppose for a contradiction that there exists a vertexu such that u~v1, u~v2 and u≁v3. Let M be the principal submatrix of AG indexed by v1,v2,v3,u, then M−θI is a principal submatrix of AG−θI and
(10)M−θI=−θ0010−θ0100−θ0110−θ.Denote byRvi the row of AG−θI indexed by the vertex vi. Since rAG−θI=3, it is clear that Rv1,Rv2,Rv3 are linearly independent, which yields that any other rows of AG−θI can be written as a linear combination of Rv1,Rv2,Rv3. Let
(11)Ru=aRv1+bRv2+cRv3.Applying (11) to the first, second, and fourth columns of M−θI, we get
(12)−aθ=1,−bθ=1,a+b=−θ,which yields that θ2=2, contradicting with Claim 1.Claim 3.
There exists no vertex adjacent to each ofv1,v2,v3.Suppose for a contradiction that there exists a vertexu such that u~vii=1,2,3. Analogous with the proof of Claim 2, let M be the principal submatrix of AG indexed by v1,v2,v3,u, then
(13)M−θI=−θ0010−θ0100−θ1111−θ.AsrAG−θI=3, then clearly Rv1,Rv2,Rv3 are linearly independent, which span the row space of AG−θI. Let
(14)Ru=aRv1+bRv2+cRv3.Applying (14) to the columns of M−θI, we get
(15)−aθ=1,−bθ=1,−cθ=1,a+b+c=−θ,which implies that θ2=3, contradicting with Claim 1. Combining the above claims, we see that if μG=3, then G is not connected, a contradiction. As a result, μG≠3. Recalling the discussions before, it can be proved that μG=2.In what follows, we prove thatG contains no induced path P4, i.e., G is a cograph. If G contains P4 as an induced subgraph, then by considering an induced subgraph of order 5 of G, we see that G must contain some Gi 1≤i≤4 (see Figure 3) as an induced subgraph (noting that μG=2). Applying Lemma 3 and Claim 1, we obtain that Gi 1≤i≤5 contains θ=−1 as an eigenvalue of multiplicity at least 2. However, by direct calculation, it follows that the multiplicity of −1 as an eigenvalue of Gi 1≤i≤5 is not more than one (see Table 2), a contradiction. Therefore, G is a cograph and the diameter diamG=2.Figure 3
The graphsGi1≤i≤5.Table 2
The eigenvalues of graphsGi1≤i≤4.
G1
-1.618
-1.618
0.618
0.618
2
G2
-1
-0.5392
-1.6751
1
2.2143
G3
-1
-0.5892
-1.7757
0.7237
2.6412
G4
-1.1701
-2
0
0.6889
2.4812
G5
-1.618
-1.4728
-0.4626
0.618
2.9354Now we are in a position to complete the proof. Note thatμG=2 and diamG=2 from the above process. Let P3=v1v2v3 be a diameter of G, then v1,v3 is a maximum independent set of G and each vertex out of v1,v3 is adjacent to at least one of v1,v3. Let
(16)Sv1=vi∈VG\VP3:vi~v1,vi≁v3,Sv2=vi∈VG\VP3:vi~v1,vi~v3,Sv3=vi∈VG\VP3:vi≁v1,vi~v3,then any vertex out of VP3 belongs precisely to one of Svi1≤i≤3. The following claims are needed for us.Claim 4.
Each vertex ofSv1 (resp., Sv3) is adjacent to each one of Sv2.Supposeu∈Sv1 and w∈Sv2 such that u≁w. Then, the vertices u,v1,w,v3 induce a path P4, a contradiction. The proof for the case of Sv3 is parallel, omitted.Claim 5.
All the vertices ofSv1 (resp., Sv3) induce a clique of G.We only prove the case ofSv1. If x,y∈Sv1 and x≁y, then x,y,v3 induce an independent set of G, contradicting with μG=2.Claim 6.
All the vertices ofSv2 induce a clique of G.Assume thatx,y∈Sv2 and x≁y. Considering an induced subgraph H of order 5 of G, we obtain that H is isomorphic to one of X1,X2,X3(see Figure 4). It follows from Lemma 3 that H contains θ as an eigenvalue of multiplicity at least 2. But Xi1≤i≤3 contains no eigenvalue of multiplicity 2 from Table 3, a contradiction.Figure 4
The graphsXi1≤i≤3.Table 3
The eigenvalues of graphsXi1≤i≤3.
X1
-2.1774
-1
0
0.3216
2.8558
X2
-2.1774
-1
0
0.3216
2.8558
X3
-2
-1.2361
0
0
3.2361From Claims4–6 and the facts μG=2 and diamG=2, we derive that G is isomorphic to the graph Γ in Figure 1, as required. The proof is completed.van Dam [14] and Huang and Huang [18] investigated the regular graphs with four distinct eigenvalues. Here, as an application of Theorem 2, we obtain a family of nonregular graphs with four distinct eigenvalues.Corollary 8.
The graphΓ with s,t,p≥1 and s+t+p=n (see Figure 1) contains four distinct eigenvalues, which is not a regular graph.Proof.
From the proof of Theorem2, we see that −1 is an eigenvalue of Γ with multiplicity n−3 and the remaining three eigenvalues of Γ are those of the quotient matrix Q of AΓ. Since detQ+I=−pst<0, then Q+I contains two positive eigenvalues and one negative eigenvalue. By the Perron-Frobenius theorem, the largest eigenvalue of Γ is simple; then, the largest eigenvalue of Q (resp., Q+I) is simple. Thus, Q+I contains three distinct eigenvalues, that is, Q contains three distinct eigenvalues. Recalling that −1 is not an eigenvalue of Q, then Γ contains four distinct eigenvalues. Moreover, it is clear that Γ is not a regular graph.



---

*Source: 3054672-2020-04-29.xml*