Trees with a large Laplacian eigenvalue multiplicity
S. Akbari E. R. van Dam M. H. Fakharan
math.CO


[2010]05C50




In this paper, we study the multiplicity of the Laplacian eigenvalues of trees.
It is known that for trees, integer Laplacian eigenvalues larger than 1 are simple and also the multiplicity of Laplacian eigenvalue 1 has been well studied before.
Here we consider the multiplicities of the other (non-integral) Laplacian eigenvalues. We give an upper bound  and determine the trees of order n that have a multiplicity that is close to the upper bound n-3/2, and emphasize the particular role of the algebraic connectivity.



Annotation-Free Cardiac Vessel Segmentation via Knowledge Transfer from Retinal Images
    Fei Yu1 Jie Zhao2 Yanjun Gong3 Zhi Wang3 Yuxi Li3 Fan Yang3 Bin Dong4,1,2 Quanzheng Li5,2 Li Zhang1,2()
    December 30, 2023
===========================================================================================================







§ INTRODUCTION


In this paper, we study the multiplicity of the Laplacian eigenvalues of trees. In particular, we are interested in upper bounds for these multiplicities, and trees with multiplicities that are close to these upper bounds.

Let G be a graph with Laplacian eigenvalues 0=μ_1≤⋯≤μ_n. Fiedler <cit.> showed that m_G(μ_1)=1 if and only if G is connected, where m_G(μ) denotes the multiplicity of Laplacian eigenvalue μ. Grone, Merris, and Sunder <cit.> proved that m_G(μ_n)=1 if G is a connected bipartite graph (in particular, if it is a tree). On the other hand, for the complete graph K_n, the multiplicity of μ_n is large and indeed is n-1. How large can the multiplicities be when we restrict to trees? It is shown by Grone et al. <cit.> that if an integer μ≥ 2 is a Laplacian eigenvalue of a tree T of order n, then m_T(μ)=1 and μ| n. Interestingly, it is different for the Laplacian eigenvalue 1, because m_G(1)≥ p(G)-q(G) for all graphs G, where p(G) and q(G) are the number of pendant vertices and quasipendant vertices, respectively, see <cit.>. For example, it follows that if G is a star (p(G)=n-1,q(G)=1), then m_G(1)=n-2. Guo, Feng, and Zhang <cit.> showed that if T is a tree of order n, then m_T(1) ∈ S={0,  1, …, n-5, n-4,  n-2} and for every integer n and every k∈ S there exists a tree T of order n with m_T(1)=k. Also Barik, Lal, and Pati <cit.> studied the multiplicity of Laplacian eigenvalue 1 in trees. In this paper we consider the multiplicities of the other (non-integral) Laplacian eigenvalues.



Our paper is further organized as follows. In Section <ref>, we introduce some notation and  definitions. We then collect some relevant results from the literature in Section <ref>. In Section <ref>, we introduce the family of trees that we will call spiders, as they will play a key role in the main part of the paper, Section <ref>. In this main part we will give an upper bound n-3/2 on the multiplicities of a Laplacian eigenvalue of a tree of order n, in particular for the algebraic connectivity, and characterize the trees that are close to this upper bound.

One main result (Theorem <ref>) — and starting point of several refinements — is that for a tree T of order n≥ 6, the multiplicity of a Laplacian eigenvalue μ≠ 1 is at most n-3/2, and we characterize the trees that attain this bound. We will also characterize the trees that have a multiplicity that is close to the upper bound (in Theorems <ref> and <ref>), and show that there are finitely many trees besides a specific family of spiders for which the algebraic connectivity has a multiplicity within a fixed range from the upper bound (in Theorem <ref>).





§ PRELIMINARIES



 §.§ Notation



Let G = (V(G),E(G)) be a graph, where V (G) = {v_1, … , v_n} is the vertex set and E(G) is the edge set. Throughout this paper all graphs are simple, that is, without loops and multiple edges. Let d_G(v_i) be the degree of v_i. We denote the non-increasing vertex degree sequence of G by (d_1, … , d_n). The maximum and minimum degree of G are denoted by Δ(G)=d_1 and δ(G)=d_n, respectively.

The adjacency matrix of G, denoted by A(G), is an n× n matrix whose (i, j)-entry is 1 if v_i and v_j are adjacent and 0 otherwise. We call L(G) = D(G) - A(G) the Laplacian matrix of G, where D(G) is the n × n diagonal matrix with d_ii=d(v_i). The eigenvalues of L(G) are called the (Laplacian) eigenvalues[Whenever we write about eigenvalues of a graph, we mean Laplacian eigenvalues (unless explicitly stated otherwise).] of G, and we denote these in increasing order by 0=μ_1(G) ≤⋯≤μ_n(G). The multiset of eigenvalues of L(G) is called the (Laplacian) spectrum of G. Fiedler <cit.> called μ_2 the algebraic connectivity of G. The multiplicity of a Laplacian eigenvalue μ in a graph G is denoted by m_G(μ); the number of Laplacian eigenvalues of G in an interval I is denoted by m_GI. We say that two (or more) Laplacian eigenvalues are conjugates (of each other) if they are roots of the same irreducible factor of the characteristic polynomial of the Laplacian (over the rationals). Conjugate eigenvalues have the same multiplicity.

A star (graph) is a complete bipartite graph K_1,n, for some positive integer n. We let P_n be the path of order n. The diameter of G is  denoted by (G). A vertex of degree one is called a pendant vertex and a vertex that is adjacent to at least one pendant vertex is called a quasipendant vertex. The number of pendant and quasipendant vertices of a graph G are denoted by p(G) and q(G), respectively.



In all of the above notation, we remove the additional G or T if there is no ambiguity; for example m(μ) instead of m_T(μ), or V instead of V(G).




 §.§ A collection of elementary results



In this section we collect and extend some relevant basic lemmas from the literature.
We start with some general ones. For other basic results, we refer to the books by Brouwer and Haemers <cit.>, Cvetković, Doob, and Sachs <cit.>, and Cvetković, Rowlinson, and Simić <cit.>.



<cit.>. If G is a connected graph with r distinct Laplacian eigenvalues, then (G)≤ r-1.



 
<cit.>. Let G be a graph of order n, with vertex degrees d_1≥⋯≥ d_n and Laplacian eigenvalues μ_1 ≤⋯≤μ_n. If G is not K_m ∪ (n-m)K_1, then μ_n-m+1≥ d_m - m+2 for 1≤ m ≤ n. In particular, if G has at least one edge, then μ_n≥ d_1+1 and if G has at least two edges, then μ_n-1≥ d_2.



We recall that a sequence μ_1 ≥⋯≥μ_m interlaces another sequence λ_1 ≥⋯≥λ_n with m < n whenever λ_i ≥μ_i ≥λ_n-m+i, for i = 1, … , m. It is well known <cit.> that the eigenvalues of a principal submatrix of a Hermitian matrix M interlace the eigenvalues of M. For the Laplacian eigenvalues, we moreover have the following two specific results.



<cit.>. Let G̃ be a graph of order n and let G be a (spanning) subgraph of G̃ obtained by removing just one of its edges. Then the n-1 largest Laplacian eigenvalues of G interlace the Laplacian eigenvalues of G̃.


A consequence of this is the following.


<cit.>. Let v be a pendant vertex of G̃ and let G=G̃∖ v. Then the Laplacian eigenvalues of G interlace the Laplacian eigenvalues of G̃.



The following results concern multiplicities.








<cit.>. Let G be a graph with p pendant vertices and q quasipendant vertices. Then m_G(1)≥ p-q.


This result follows from the observation that for every pair (v_i,v_j) of pendant vertices that is adjacent to the same quasipendant vertex, the difference e_i-e_j of the corresponding characteristic vectors is an  eigenvector of L(G) for eigenvalue 1. This gives p-q linearly independent eigenvectors.




Finally, we have some specific results for trees.


<cit.>. Let T be a tree with p pendant vertices. If μ is a Laplacian eigenvalue of T, then m_T(μ) ≤ p-1.


The following is a clear generalization to non-integral eigenvalues of a result by Grone, Merris, and Sunder <cit.>. It uses the Matrix-Tree theorem, which states that any cofactor of the Laplacian matrix of G equals the number of spanning trees of G. In case of trees, this is equivalent to the fact that the product of all non-zero Laplacian eigenvalues equals the number of vertices; we shall use this also later.



Let μ be a Laplacian eigenvalue of a tree T with m_T(μ)>1. Then the product of μ and its conjugate eigenvalues equals 1. In particular, if μ is an integer, then μ=1.



Let v be a pendant vertex. Then the Laplacian matrix of T has the form

    L(T)=[ B *; 1 ],

where B is the principal submatrix corresponding to T∖ v. Since m_T(μ)>1, there is an eigenvector x of L(T) for μ such that its last component is 0.  If x' is the vector obtained from x by deleting the last component, then it is not hard to see that Bx'=μ x'. So μ is an eigenvalue of B as well (and so are its conjugates). By the Matrix-Tree Theorem however, we have that (B)=1, and the result follows.


To conclude this section, we mention a bound for the multiplicity of the algebraic connectivity of a tree. It follows easily from a result of Grone and Merris <cit.>.

Let T be a tree with   Δ≥ 2. Then m_T(μ_2)≤Δ -1.



Let m=m_T(μ_2), and suppose that m≥Δ. Because the multiplicity is at least 2, there is an eigenvector that has value 0 corresponding to  one of the vertices, and so T is a so-called type I tree (see <cit.>). By <cit.>, the so-called characteristic vertex of T has degree at least m+1, but this is at least Δ+1, which is a contradiction.





§ SPIDERS AND THEIR SPECTRA


In this section we define two families of trees that are most relevant to our results. We start with the main one, i.e., the family of trees that have large multiplicities for some non-integral Laplacian eigenvalues.

The spider T(s,k), with 1≤ k ≤ s, is defined as in Figure <ref>. It is obtained from the star K_1,s by extending k of its rays (legs) by an extra edge, and has n=s+k+1 vertices. We say that the spider has k legs.









The Laplacian spectrum of T(k,k) is

    {0^[1], ^[k-1], λ_1^[1], ^[k-1], λ_2^[1]},

where (, )=(3-√(5)/2,3+√(5)/2) and λ_1, λ_2 are the roots of  x^2-(k+3)x+2k+1.



In Figure <ref>, an eigenvector for eigenvalue =3-√(5)/2 is shown[Whenever we use  and  in this paper, we mean the specific values 3-√(5)/2 and 3+√(5)/2.]. It is clear that there are k-1 linearly independent such eigenvectors corresponding to the eigenvalue . Similarly, we find k-1 linearly independent eigenvectors corresponding to eigenvalue =3+√(5)/2.
Because μ_1=0, there are only two other eigenvalues λ_1 ≤λ_2. Because the product of all non-zero eigenvalues equals n=2k+1, it follows that λ_1 λ_2 =2k+1. Noting the trace of L (which equals twice the number of edges) it follows that λ_1 + λ_2 =k+3, and the result follows.


Note that if we let λ_2 >λ_1, then λ_1>1 and λ_2>, so for k ≥ 2 the algebraic connectivity μ_2 equals 3-√(5)/2 and μ_n-1=3+√(5)/2. Proposition <ref> thus shows that the upper bound of Proposition <ref> is sharp.



The Laplacian spectrum of T(s,k) with k<s is

    { 0^[1], ^[k-1], λ_1^[1],  1^[s-k-1], λ_2^[1], ^[k-1], λ_3^[1]},

where (, )=(3-√(5)/2,3+√(5)/2) and λ_1, λ_2, λ_3 are the roots of x^3-(s+4)x^2+(3s+4)x-(s+k+1).


 As before, we have eigenvalues  and  with multiplicities at least k-1, and eigenvalue 0. In addition, we have eigenvalue 1 with multiplicity at least s-k-1 by Lemma <ref>. Thus, three eigenvalues λ_1, λ_2,λ_3 are left. Again, from the product of all non-zero eigenvalues being equal to n, it follows that   λ_1 λ_2 λ_3 = n= s+k+1. Moreover, λ_1+λ_2 +λ_3= 2n-2-(s-k-1)-3(k-1)=s+4. A quadratic equation easily follows from the trace of L^2:

    ∑_i=1^n μ_i^2= ∑_i=1^n d_i^2 + 2m

for every graph G of order n with m edges, and degrees d_i. For T(s,k), we obtain that
λ_1^2+λ_2^2 +λ_3^2= s^2+2s+8, and from this we conclude that λ_1 λ_2 + λ_1 λ_3 +λ_2 λ_3 = 1/2(s+4)^2-1/2(s^2+2s+8) = 3s+4. From all of this, the spectrum follows.


Note that for a fixed integer s, one can use induction to show that μ_2(T(s,s-i))≥ and μ_n-1(T(s,s-i))≤, for i=0, … , s-1, starting from Proposition <ref> and by inductively applying Lemma <ref>. On the other hand, for fixed k≥ 2, it also follows by induction that μ_n-1(T(k+i,k))≥ for all i. Consequently, we have the following.

 Let T=T(s,k), with s ≥ k ≥ 2. Then μ_2(T)= =3-√(5)/2 and μ_n-1(T)= =3+√(5)/2.


It also follows from the above that μ_2(T(s,1))> for s≥ 1.
Below we will show that the spider graphs T=T(s,k), with s ≥ k ≥ 2 are extremal regarding the eigenvalues  and .

Observe first however that if k=s-1 then m_T(1)=0 and λ_2=2. So in this case, λ_1 and λ_3 are the roots of x^2-(s+2)x+s and the spectrum of T(s,s-1) is

    {0^[1], ^[s-2], λ_1^[1],  2^[1], ^[s-2], λ_3^[1]}.





A second family of trees that we will use is shown in Figure <ref>. Such a tree H(s, r, t)  is obtained by attaching s pendant vertices to one end point of the path on r vertices, and t pendant vertices to its other end point, for some positive integers s,r,t. We note that for r=1, we obtain a star (a tree with diameter 2). The Laplacian spectrum of this graph is {0^[1],  1^[n-2],  n^[1]}. Also, every tree of order n with diameter 3 is a graph H(s,2,t) for some integers s, t such that s+t=n-2. The spectrum of this graph can easily be obtained in a similar way as in Proposition <ref>.




<cit.>. Let T=H(s,2,t) be of order n=s+t+2. Then the characteristic polynomial of L(T) is
x(x-1)^n-4[x^3-(n+2)x^2+(2n+st+1)x-n].


In order to prove some of the results in the next section, we need the following two half-known characterizations of trees with extremal Laplacian eigenvalues 3 ±√(5)/2. The first is a result by Li, Guo, and Shiu <cit.>. For completeness, we provide a shorter proof of this result.




<cit.>.
Let G be a connected graph of order n. Then μ_n-1(G)=3+√(5)/2 if and only if G≅ T(s,k) for some positive integers s,k with k≥ 2.



One side is clear by Lemma <ref>. To show the other side, suppose that μ_n-1(G)=3+√(5)/2=. If Δ(G)=2, then G is a path or a cycle. Since μ_5(P_6)=3>, it follows from interlacing (Lemmas <ref> and <ref>) that the order of G is less than 6, and then it can be checked that G≅ P_5 = T(2,2). Next, assume that u is a vertex of G with degree Δ(G)≥ 3. If there exists a vertex v at distance 2 from u with degree at least 2, then the graph G can be obtained from the fork F in Figure <ref> by adding some pendant vertices and some edges. But μ_5(F) =3> and so again by interlacing, we have that μ_n-1(G)≥μ_5(F) >, which is a contradiction. Thus, every vertex of degree at least 2 is adjacent to u. By Lemma <ref>, we have d_2(G)≤μ_n-1, hence d_2(G) ≤ 2. So G≅ T(s,k) for some integers s,k. By Proposition <ref>, it is necessary to have k≥ 2.


We note that the proof actually shows that if μ_n-1(G) ≤3+√(5)/2, then G is a star or a spider. For more details and the full classification of graphs with μ_n-1(G) ≤ 3, we refer to Li, Guo, and Shiu <cit.>. The following similar result is a strengthening of a result by Zhang <cit.>.




Let T be a tree of order n. If μ_2(T) ≥3-√(5)/2, then T is a star, a spider, H(2,2,2), or H(3,2,2), and equality holds if and only if T≅ T(s,k) for some positive integers s,k, with k≥ 2.



Suppose that μ_2(T) ≥3-√(5)/2=. By interlacing (Lemma <ref>), the tree T cannot have P_6 as a subgraph since μ_2(P_6)<, so (T)≤ 4. If T is not a star, then it must have diameter 3 or 4. If (T)=3, then T is H(s,2,t) for some positive integers s,t. Using Lemma <ref>, we find however that μ_2(H(3,2,3)) < and μ_2(H(4,2,2)) <, so it follows again by interlacing that in this case T can only be one of the trees H(2,2,2), H(3,2,2), and T(s,1), for some positive integer s. Indeed, μ_2(H(2,2,2)) >, μ_2(H(3,2,2)) >, and μ_2(T(s,1))>.

Finally, suppose that (T)=4. For the fork F (see Figure <ref>), we have μ_2(F)<. So T cannot have F as a subgraph, and thus T is a spider. The case of equality now follows from Lemma <ref> and the fact that a star, H(2,2,2), H(3,2,2), and T(s,1) all have μ_2>.






§ TREES WITH A LARGE MULTIPLICITY





We are now ready for our main results, that is, to bound the multiplicities of non-integer Laplacian eigenvalues of trees, and to characterize the trees with large Laplacian eigenvalue multiplicities.



Let T be a tree of order n≥ 6 with a Laplacian eigenvalue μ. If μ≠ 1, then m_T(μ)≤n-3/2, and equality holds if and only if T≅ T(n-1/2,n-1/2) and μ =3 ±√(5)/2. In particular, if equality holds, then μ is the algebraic connectivity of T or its conjugate.



Suppose that m_T(μ) > n-3/2 and μ≠ 1. Then m_T(μ)>1. So  by Lemma <ref>, the eigenvalue μ is not an integer, so it has at least one conjugate eigenvalue μ with m_T(μ)=m_T(μ). So m_T(μ)≤n-1/2. If n is odd, then m_T(μ) =n-1/2, so T has exactly 3 distinct eigenvalues. This implies that the diameter of T is at most 2 (by Lemma <ref>), so T is a star, with spectrum { 0^[1],  1^[n-2],  n^[1]}, which is a contradiction.

So n is even and m_T(μ)=n-2/2. Hence T has spectrum

    { 0^[1], μ^[n-2/2], μ^[n-2/2], λ^[1]}

for some eigenvalue λ. Now, by Lemma <ref>, T has diameter at most 3, and it is not a star. So T has p=n-2 pendant vertices and q=2 quasipendant vertices. Thus, m_T(1)≥ p-q=n-4 ≥ 2, by Lemma <ref>, which is a contradiction, so m_T(μ) ≤n-3/2.

Now, suppose that m_T(μ)= n-3/2. Again, by Lemma <ref>, the eigenvalue μ is not an integer.
If n=7, then possibly μ can have two conjugate eigenvalues. However, this would imply  that T has four distinct eigenvalues, which would give a contradiction in the same way as in the above case of n even. So n ≥ 7 and μ has exactly one conjugate eigenvalue μ. By Lemma <ref>, we have μμ=1. So the spectrum of T is

    {0^[1], μ^[n-3/2], μ^[n-3/2], λ_1^[1], λ_2^[1]},

for some eigenvalues λ_1 and λ_2. Since the product of all non-zero eigenvalues of a tree equals n, we find that λ_1λ_2=n. Because the only tree on n vertices with an eigenvalue n is the star (which easily follows by observing that the complement of such a tree should be disconnected), it follows that m_T(1)=0, and hence by Lemma <ref>, we deduce that p=q. Moreover, by Lemma <ref> the diameter of T is at most 4. Because n is odd, it now easily follows that T is isomorphic to T(n-1/2,n-1/2). As observed in Proposition <ref>, this graph indeed has an eigenvalue (in fact, the two conjugates 3±√(5)/2) with multiplicity n-3/2.


Note that if T is a tree but not a star, then (T) ≥ 3. Because μ_2(P_4)<1, it then follows by interlacing that μ_2(T)<1, so we have the following.


If T is a tree of order n but not a star, then m_T(μ_2)≤n-3/2.



The multiplicity of μ_2 in a star K_1,n equals n-1 and by Corollary <ref>, m_T(μ_2)≤⌊n-1/2⌋ -1 for every other tree T. So there is a huge gap between these multiplicities n-1 and ⌊n-1/2⌋ -1.
Lemma <ref> and Proposition <ref> show that there are no other gaps. In fact, for any i=1,…, ⌊n-1/2⌋ -1, the tree T=T(n-i-2,i+1) has m_T(μ_2)=i.


In Theorem <ref>, we will show that for every positive integer j, all except finitely many trees T with m_T(μ_2)=⌊n/2⌋ -j are spiders. But first, we determine the typical values of the Laplacian eigenvalues with large multiplicity.




Let j be an integer with j ≥ 2. If T is a tree of order n> 10j and m_T(μ)= ⌊n/2⌋ -j for a Laplacian eigenvalue μ≠ 1, then μ =3 ±√(5)/2.



Suppose that n≥ 10j+1 and m_T(μ)=⌊n/2⌋ -j. Because μ cannot be integer, there exists another (conjugate) eigenvalue μ with m_T(μ)=⌊n/2⌋ -j. Since n≥ 10j+1 there can be no other (conjugate) eigenvalue with such a large multiplicity. Thus, μ and μ are the roots of a quadratic factor of the Laplacian polynomial, so μ + μ equals a positive integer t, say. Because μμ=1 by Lemma <ref>, it follows that t ≥ 3. Since μ_1+⋯ +μ_n =2n-2, we have that
(⌊n/2⌋ -j)t < 2n-2.

First suppose  that t≥ 5. If n is even, then it follows that n<2jt-4/t-4≤ 10j-4, which is a contradiction. Similarly, if n is odd, then n<(2j+1)t-4/t-4≤ 10j+1; again a contradiction.
Next, suppose that t=4. Note that by Proposition <ref> and Lemma <ref>, we have Δ≥⌊n/2⌋ -j +1 and μ_n ≥Δ +1, and hence  μ_n ≥⌊n/2⌋ -j+2. Note also that μ_n is a simple eigenvalue by <cit.>, so it is not equal to μ or μ. If n is even, then

    ∑_μ_i ∉{μ, μ}μ_i = 4j-2 >  n/2 -j+2

and so n<10j-8, which is a contradiction.
Similarly, if n is odd, then

    ∑_μ_i ∉{μ, μ}μ_i = 4j > n-1/2 -j+2

and so n<10j-3; again a contradiction.

Thus, t= 3 and hence μ ,μ = 3 ±√(5)/2.




Let j be an integer with j≥ 2 and let T be a tree of order n> 10j. Then m_T(μ_2)= ⌊n/2⌋ -j if and only if T ≅ T(⌈n/2⌉ +j-2, ⌊n/2⌋ -j+1).



If m_T(μ_2)= ⌊n/2⌋ -j, then T is not a star, so μ_2 ≠ 1, and hence by Lemma <ref>, we have μ_2= 3-√(5)/2. Now, by Proposition <ref>, it is clear that T≅ T(s,k) for some suitable s and k. These integers are now determined by the multiplicity of μ_2 (see Propositions <ref> and <ref>), which finishes the proof.


Observe the contrast between Theorems <ref> and <ref> in the sense that in the latter we restrict to eigenvalue μ_2. Indeed, the following examples show that this restriction is necessary, at least for j ≥ 3.





Let s ≥ k ≥ 2 and let T^*=T^*(s,k) be the tree obtained from T(s,k) by adding one pendant vertex to one of the k legs. See Figure <ref> for the case k=2. It is clear from Proposition <ref> that μ_2(T^*)<, and it follows from interlacing (Lemma <ref>) that m_T^*() equals k-2 or k-1. We claim that this multiplicity equals k-2. In order to show this, we first consider the case k=2 and show that  is not an eigenvalue of T^*(s,2) for any s ≥ 2.

Indeed, suppose that  is an eigenvalue of T^*(s,2) with eigenvector x. By normalizing the entry x_1=1 of the top right vertex in Figure <ref>, and applying the equation Lx= x, we recursively find the entries of x as given in the figure (we omit the technical details; note also that it easily follows that x_1 cannot be zero). But then finally for the bottom two right vertices (where we obtained x_n-1=x_n=-1) we should have the equation x_n-x_n-1= x_n, which gives a contradiction.

Next, consider the general case T^*(s,k), and suppose that it has eigenvalue  with multiplicity k-1, for k≥ 3. By interlacing it then follows that T^*(s,k-1) has eigenvalue  with multiplicity at least k-2, and by repeating this, we find that T^*(s,2) has eigenvalue  with multiplicity at least 1, which is a contradiction, and hence confirms our claim.

For even n, we can now take s=n/2+j-4 for j ≥ 3, to obtain m_T^*()=n/2-j. For odd n, we take  s=n-1/2+j-3 for j ≥ 3, to obtain m_T^*()=n-1/2-j. Thus, for every j ≥ 3 there are infinitely many trees with such multiplicities.


In the given examples, we cannot take j=2. Indeed, for this case we can prove something stronger than in Theorem <ref>, and obtain a result that is similar to Theorem <ref>. Here we will show that there are unique trees of order n with multiplicities n/2-2 and n-1/2-2 for an eigenvalue μ≠ 1.


Let T be a tree of order n≥ 8 and μ≠ 1 be a Laplacian eigenvalue of T. Then m_T(μ)= n/2 -2 if and only if T≅ T(n/2, n/2 -1) and μ=3±√(5)/2.
In particular, in this case μ is the algebraic connectivity of T or its conjugate.


 One side of the equivalence is clear from Proposition <ref>. To show the other side, we will first show by induction on n (with n even) the claim that if m_T(μ)= n/2 -2, then μ=3±√(5)/2 and that  μ_2(T)==3- √(5)/2. We checked that this is true for n=8 by enumerating all trees of this order with the Sage computer package.
For n>8, consider a tree T with m_T(μ)= n/2 -2. Consider one of its extremal quasipendant vertices v (in the sense that v becomes pendant in the tree that is obtained from T by removing all its pendant vertices). Now, remove the edge that connects v to its (unique) non-pendant neighbor. The remaining graph is a disjoint union of a star (with center v) and a tree T' on t vertices, say. By interlacing (Lemma <ref>), it follows that m_T'(μ) ≥n/2-3. But m_T'(μ) ≤t-3/2 by Theorem <ref>, so it follows that t ≥ n-3. Because n-t ≥ 2, we have two cases. If t=n-3, then m_T'(μ) = t-3/2, and it follows from Theorem <ref> that indeed μ=3±√(5)/2 and μ_2(T')=, which implies by interlacing that μ_2(T)=. If t=n-2, then m_T'(μ) = t/2-2, so by induction μ=3±√(5)/2 and μ_2(T')=, but the latter (and interlacing) again implies that μ_2(T)=, which finishes the proof of our claim.

Just like in the proof of Theorem <ref>, we can now apply Proposition <ref> to finish the proof.


We omit the proof of the following similar result, as the proof is very similar, although we also have to use Theorem <ref> now.


Let T be a tree of order n≥ 9 and μ≠ 1 be a Laplacian eigenvalue of T. Then m_T(μ)= n-1/2 -2 if and only if T≅ T(n-1/2+1, n-1/2 -1) and μ=3±√(5)/2.
In particular, in this case μ is the algebraic connectivity of T or its conjugate.


We note that one could try to extend this result further, and indeed, the induction steps work over and over again, so induction would give a theorem about multiplicity ⌊n/2⌋ -j for each j ≥ 2, if only the bases of the induction steps would be true. Of course, this is where things go wrong. For example, we cannot prove a similar result for multiplicity n/2 -3 and n ≥ 10 because we have counterexamples such as T^*(4,4) on 10 vertices. Indeed, there are five such counterexamples, and we depict them in Figure <ref>. Besides T^*(4,4) (Fig. <ref>a), there are (exactly) two other trees of order 10 that have eigenvalue  with multiplicity 2 and μ_2(T)< (Fig. <ref>b and c). Moreover, there is one tree of order 10 with eigenvalues 2 ±√(3) with multiplicity 2 (Fig. <ref>d), and one tree of order 10 that has the roots of x^3-5x^2+6x-1 as eigenvalues with multiplicity 2 (Fig. <ref>e). The variety of these examples shows that further classification of trees with an eigenvalue other than 1 with multiplicity ⌊n/2⌋ -j for j ≥ 3 (on top of Lemma <ref> and Theorem <ref>) seems unfeasible.




Acknowledgement. The research of the first author was partly funded by Iran National Science Foundation (INSF) under the contract No. 96004167. Also, part of the work in this paper was done while the third author was visiting Tilburg University.








99

barikS. Barik, A.K. Lal, S. Pati, On trees with Laplacian eigenvalue one, Linear and Multilinear Algebra. 56:6 (2008) 597-610.

haemerA.E. Brouwer, W.H. Haemers, A lower bound for the Laplacian eigenvalues of a graph-Proof
of a conjecture by Guo, Linear Algebra Appl. 429 (2008) 2131-2135.

BH A.E. Brouwer, W.H. Haemers, Spectra of Graphs, Springer, New York, 2012;
    <http://homepages.cwi.nl/ aeb/math/ipm/>.



CDSD. Cvetković, M. Doob, H. Sachs, Spectra of Graphs, Academic Press, New York, 1980.

cvetD. Cvetković, P. Rowlinson, S. Simić, An Introduction to the Theory of Graph Spectra, Cambridge University Press, New York, 2010.

far I. Faria, Permanental roots and the star degree of a graph, Linear Algebra Appl. 64 (1985) 255-265.


fiedler M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal. 23 (2) (1973) 298-305.

Grone R. Grone, R. Merris, Ordering trees by algebraic connectivity, Graphs and Combinatorics. 6 (1990) 229-237.

kamelR. Grone, R. Merris, V.S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (2) (1990) 218-238.

merrisR. Grone, R. Merris, Algebraic connectivity of trees, Czechoslovak Mathematical Journal. 37 (4) (1987) 660-670.

feng J.M. Guo, L. Feng, J.M. Zhang, On the multiplicity of Laplacian eigenvalues of graphs, Czechoslovak Mathematical Journal. 60 (135) (2010) 689-698.



hwa S.G. Hwang, Cauchy's interlace theorem for eigenvalues of Hermitian matrices, The American Mathematical Monthly. 111 (2) (2004) 157-159.

li J. Li, J.M. Guo, W.C. Shiu, On the second largest Laplacian eigenvalues of graphs, Linear Algebra Appl. 438 (2013) 2438-2446.



zhang X.D. Zhang, On the two conjectures of Graffiti, Linear Algebra Appl. 385 (2004) 369-379.










