%% Antes de processar este arquivo LaTeX (LaTeX2e) deve %% verificar que o arquivo TEMA.cls estah no mesmo %% diretorio. O arquivo TEMA.cls pode ser obtido do %% endereco www.sbmac.org.br/tema. \documentclass{TEMA} %\usepackage[brazil]{babel} % para texto em Português \usepackage[english]{babel} % para texto em Inglês %\usepackage[latin1]{inputenc} % para acentuação em Português %\input{P-margin.inf} %\usepackage[dvips]{graphics} \usepackage{graphics} \usepackage{graphicx} \usepackage{subfigure} \usepackage{epsfig} \usepackage{amssymb,amsmath} \newcommand{\B}{{\tt\symbol{92}}} \newcommand{\til}{{\tt\symbol{126}}} \newcommand{\chap}{{\tt\symbol{94}}} \newcommand{\agud}{{\tt\symbol{13}}} \newcommand{\crav}{{\tt\symbol{18}}} \newtheorem{example}[thmTEMA]{Example} \newcommand{\nor}{\mathcal{L}} \def\Lp{L^{\mkern -18mu D}} \newcommand{\R}{\mathbb{R}} \newcommand{\om}{\omega} \begin{document} %******************************************************** \title {Locating Eigenvalues of Perturbed Laplacian Matrices of Trees%} \thanks{This work was presented at CNMAC 2016, Brazil.}} \author {R. O. BRAGA% \thanks{rodrigob@unisinos.br; This work is part of the doctoral studies of this author.}\,, Ciências Exatas e Tecnológicas, UNISINOS, Av. Unisinos, 950, 93022-000 São Leopoldo, RS, Brasil \\ \\ V. M. RODRIGUES% \thanks{vrodrig@mat.ufrgs.br.}\,, Departamento de Matemática Pura e Aplicada, IME - UFRGS, Av. Bento Gonçalves, 9500, 91509-900 Porto Alegre, RS, Brasil } \criartitulo \runningheads {Braga and Rodrigues}{Locating Eigenvalues of Perturbed Laplacian Matrices} \begin{abstract} {\bf Abstract}. We give a linear time algorithm to compute the number of eigenvalues of any perturbed Laplacian matrix of a tree in a given real interval. The algorithm can be applied to weighted or unweighted trees. Using our method we characterize the trees that have up to $5$ distinct eigenvalues with respect to a family of perturbed Laplacian matrices that includes the adjacency and normalized Laplacian matrices as special cases, among others. {\bf Keywords}. Perturbed Laplacian matrix, eigenvalue location, trees \end{abstract} %******************************************************** \newsec{Introduction} The \textit{Spectral Graph Theory} studies the relations between the spectrum of matrices associated to graphs and structural properties of the graphs. The most commonly used representation matrix of a graph is the \textit{adjacency matrix}. If $G$ is a simple undirected graph with vertices $v_1, v_2, \ldots, v_n$, the adjacency matrix $A = (a_{ij}) $ of $G$ is the real symmetric matrix of order $n$ with entries $0$ or $1$, where $a_{ij} = 1$ if and only if vertices $v_i$ and $v_j$ are adjacent. A \textit{tree} is a connected graph with no cycles. In 2011, Jacobs e Trevisan \cite{Jac11} gave a linear time algorithm to compute the number of eigenvalues of a tree in a given real interval. Their method has the important advantage of being executed directly on the tree with so that the matrix is not needed explicitly. The authors observed that the algorithm had potential to be adapted to other matrices, for instance the \textit{Laplacian matrix}, defined as the matrix $L = D_G - A$, where $D_G$ é the diagonal matrix whose diagonal entry $ii$ is the degree $d_i$ of vertex $v_i$ of a graph $G$ and $A$ is the adjacency matrix of $G$. In fact, the algorithm of Jacobs and Trevisan and the extensions that followed it became a practical and efficient tool in Spectral Graph Theory. We notice in particular the work of Fritscher \textit{et al.} \cite{Fri11}, where the original algorithm was adapted for the Laplacian matrix of a tree and applied to prove that among all trees with $n$ vertices, the star $S_n$ has the highest \textit{Laplacian energy}, which was conjectured by Radenkovi\'{c} and Gutman in \cite{Rad}. Besides, Braga \textit{et al.} adapted the original algorithm for the \textit{normalized Laplacian matrix}, introduced by Chung \cite{chung} as the matrix $ \mathcal{L}= (\ell_{ij})$, where $\ell_{ij} = 1$ if $i=j$ and $d_i > 0$, $\ell_{ij} = -\frac{1}{\sqrt{d_i \cdot d_j}}$, if vertices $v_i$ and $v_j$ are adjacent, and $\ell_{ij}=0$, otherwise. This variation of the algorithm was used to study the multiplicity of normalized Laplacian eigenvalues of small diameter trees, which allowed the authors to characterize the trees that have up to $5$ distinct normalized Laplacian eigenvalues. The results obtained with the localization algorithm for different representation matrices of trees motivated the development of an algorithm to localize the eigenvalues of a tree for a more general class of matrices, generalizing the previous algorithms, which is the aim of this work. A \textit{weighted graph} is a graph where a real number $\omega (e_{i j}) = \omega_{i j}$ is assigned to each edge $e_{i j}$ connecting vertices $v_i$ and $v_j$. We say that $\omega_{i j}$ that is the \textit{weight} of edge $e_{i j}$. An unweighted graph can be considered as a graph where all edges have weight $1$. In \cite{Bap01}, Bapat \textit{et al.} defined the \textit{perturbed Laplacian matrix} of a graph with positive weights, which encompasses the adjacency, Laplacian and normalized Laplacian matrices, among others. Given a real diagonal matrix $D$, the perturbed Laplacian matrix of $G$ with respect to $D$, is the matrix $$\Lp(G)= D - A,$$ where $A=(a_{ij})$ is the adjacency matrix of $G$, with $a_{ij} = \omega_{i j}$ if vertices $v_i$ and $v_j$ are adjacent, and $0$ otherwise. The localization algorithm for the perturbed Laplacian matrix of a tree, that we present in Section $2$, beyond preserving the practicality of the original algorithm and its extensions, has the advantage of allowing to simultaneously derive results for several representation matrices. In addition, our method enables to work with weighted trees, which was not possible before. In Section $3$ we apply our method to characterize the trees that have up to $5$ distinct eigenvalues with respect to a family of perturbed Laplacian matrices that includes the adjacency and normalized Laplacian matrices as special cases, among others. \newsec{Locating Eigenvalues of Perturbed Laplacian Matrices} \label{algperturbed} Taking as input a weighted tree $T$ of order $n$, a scalar $ \alpha \in \R $ and a real diagonal matrix $D$, the algorithm $\textit{DiagonalizeW}(T, \alpha)$ that we present in this section diagonalizes the matrix $\Lp(T) + \alpha I$, where $ \Lp(T)$ is the perturbed Laplacian matrix of $T$ with respect to $D$. The output is a diagonal matrix $D_{\alpha}$ \textit{congruent} to $\Lp(T) + \alpha I$. We recall that two square matrices of order $n$, $A$ and $B$, are congruent if there is an invertible matrix $P$ such that $ A = P^T B P $. Like the original algorithm of Jacobs and Trevisan for the adjacency matrix, our method is executed directly on the tree $T$, so that the matrix is not needed explicitly. The tree $T$ is rooted at an arbitrary vertex and the vertices are ordered $v_1, \ldots, v_n $, so that if $v_j$ is a child of $v_k$, then $ j>k $. Thus the root is the vertex $v_1$. Every vertex $v$ of $T$, except for the root, has a \textit{parent}, which is the vertex adjacent to $v$ that is not a child of $v$. During the execution the algorithm assigns, to each vertex $v_i$ of $T$, a real value $a(v_i)$ which at the end corresponds precisely to the entry $ii$ of the diagonal matrix $D_{\alpha}$. We call $a (v_i)$ the \textit{diagonal value} of vertex $v_i$. Initially, each $v_i$ receives the diagonal value $a(v_i) = \delta_i + \alpha$, where $\delta_i$ is the entry $ii$ of the diagonal matrix $D$. Then the vertices are processed bottom-up, towards the root, as shown in Figure \ref{treealgo}. For a vertex $v_k$, we denote by $\mathcal{C}_k$ the set of all children of $v_k$. If $v_k$ is a leaf which is not the root, then $\mathcal{C}_k = \emptyset $. \vspace{-0.1cm} \begin{figure}[h!] \centering {\tt\begin{tabular}{p{14cm}} Input: weighted tree $T$ with ordered vertices $v_1, v_2, ..., v_n$, scalar $\alpha$, \\ $\> \> \> \>\> \> \> \>\> \> \> \> \> \> \> \> $ diagonal matrix $D$. \\ Output: diagonal matrix $D_{\alpha}$ congruent to $\Lp(T) + \alpha I$. \\ %$\> %\> \> \>\> \> \> \>\> \> \> \> \> \> \> \> \> $ $\Lp(T) + \alpha I$. \\ \\ $\> \> \> \> $Initialize $a(v_{i}) := \delta_{i} + \alpha$, for each vertex $v_i$. \\ $\> \> \> \> $\textbf{For} $k=n$ to $1$ \\ $\> \> \> \> \> \> \> \> $\textbf{if} $v_k$ is not a leaf then \\ $\> \> \> \> \> \> \> \> \> \> \> \>$ \textbf{1.} \textbf{if} $a(v_i) \neq 0$, for all $v_i \in \mathcal{C}_k$, then \\ $\> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> $ $a(v_k) \leftarrow a(v_k) - \displaystyle\sum_{v_{i} \in C_k} {\frac{(\omega_{i k} )^2}{a(v_i) }}.$ \\ $\> \> \> \> \> \> \> \> \> \> \> \>$ \textbf{2.} \textbf{if} $a(v_i) =0$ for some $v_i \in \mathcal{C}_k$, then \\ $\> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> $ select one vertex $v_j$ in $\mathcal{C}_k$ for which $a(v_j) = 0;$ \\ $\> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> $ $a(v_k) \leftarrow - \displaystyle\frac{(\omega_{j k})^{2}}{2}; \,\,\,\, a(v_j) \leftarrow 2;$ \\ $\> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> \> $ if $v_k$ has a parent $v_{\ell}$, remove the edge $v_k v_{\ell}$. \\ $\> \> \> \> $ Print $a(v_1), a(v_2), ..., a(v_n)$. \end{tabular} } \vspace{-0.2cm} \caption{ Algorithm $\textit{DiagonalizeW}(T, \alpha)$.} \label{treealgo} \end{figure} \vspace{-0.1cm} To understand how the procedure above computes the diagonal values of a diagonal matrix congruent to the matrix $\Lp(T) + \alpha I$, let us consider a vertex $v_k$ of $T$ with a child $v_j$, which corresponds to the entries in the matrix below: $$\small {\begin{array}{c} \\ k \\ \\ j \\ \\ \end{array} \left[ \begin{array}{ccccc} & \vdots & & \vdots & \\ \cdots & a(v_k) & \ldots & \omega_{k j} & \cdots \\ & \vdots & \ddots & \vdots & \\ \cdots & \omega_{ j k } & \cdots & a(v_j) & \cdots \\ & \vdots & & \vdots & \end{array} \right]} . $$ If $a(v_j) \neq 0$, then the following row and column operations annihilate the entries $kj$ and $jk$: $$ R_k \leftarrow R_k - \frac{\omega_{ j k }}{a(v_j)} R_j \;\;\mbox { and }\;\; C_k \leftarrow C_k - \frac{\om_{ j k }}{a(v_j)} C_j .$$ After these two operations, the corresponding entries of the matrix are $$ \small {\begin{array}{c} \\ k \\ \\ j \\ \\ \end{array} \left[ \begin{array}{ccccc} & \vdots & & \vdots & \\ \cdots & a(v_k) - \frac{(\om_{ k j })^2}{a(v_j)} & \ldots & 0 & \cdots \\ & \vdots & \ddots & \vdots & \\ \cdots & 0 & \cdots & a(v_j) & \cdots \\ & \vdots & & \vdots & \end{array} \right]} . $$ Note that if $v_k$ has all children with nonzero diagonal values, each of them may be used to annihilate the two off-diagonal entries that correspond to its connection with $v_k$. Hence, after performing the same operations for all children of $v_k$, the diagonal value of $v_k$ becomes $$a(v_k) - \sum_{v_i \in C_{k}} \frac{(\om_{ i k })^2}{a(v_i)},$$ which corresponds to the value assigned by the algorithm in this case (Step 1). Suppose that $v_k$ has a child $v_j$ with $a(v_j)=0$, as in the submatrix below. Then vertex $v_j$ may be used to annihilate the two off-diagonal entries of any other child $v_i$ of $v_k$, as well as the two entries representing the edge between $v_k$ and its parent $v_{\ell}$, in the case $v_k$ is not the root, as follows. Note that at this point $v_k$ and $v_\ell$ still have their initial diagonal values, since the vertices are processed bottom-up. $$ {\begin{array}{c} \ell \\ k \\ j \\ i \end{array} \left[ \begin{array}{cccc} \delta_{\ell} + \alpha & \omega_{\ell k} & & \\ \om_{ k \ell } & \delta_{k } + \alpha & \om_{ k j} & \om_{ k i} \\ & \om_{ j k } & 0 & \\ & \om_{ i k } & & a(v_i) \end{array} \right]} .$$ The operations $$ R_i \leftarrow R_i - \frac{\om_{i k }}{\om_{ j k }} R_j \;\;\mbox { and }\;\; C_i \leftarrow C_i - \frac{\om_{k i}}{\om_{ k j}} C_j, $$ annihilate the entries $i k$ and $ k i$, while the operations below annihilate the entries $\ell k$ and $k \ell$: $$ R_{\ell} \leftarrow R_{\ell} - \frac{\om_{ \ell k}}{\om_{ j k }} R_j \;\;\mbox { and }\;\; C_{\ell} \leftarrow C_{\ell} - \frac{\om_{k \ell }}{\om_{k j }} C_j. $$ Note that $\om_{ j k }=\om_{ k j } \neq 0$, since $v_j$ is a child of $v_k$. These last two operations effectively remove the edge between $v_k$ and its parent $v_{\ell}$, disconnecting the graph, which is performed in Step 2 of the algorithm. At this point, the submatrix with rows and columns $i, j, k, \ell $ has been transformed as $$ {\begin{array}{c} \ell \\ k \\ j \\ i \end{array} \left[ \begin{array}{cccc} \delta_{\ell} + \alpha & 0 & & \\ 0 & \delta_{k} + \alpha & \om_{ k j} & 0 \\ & \om_{ j k } & 0 & \\ & 0 & & a(v_i) \end{array} \right]}.$$ Next, the operations $$ R_{k} \leftarrow R_{k} - \frac{(\delta_{k} + \alpha)}{2 \om_{j k} } R_j \;\;\mbox { and}\;\; C_{k} \leftarrow C_{k} - \frac{(\delta_{k} + \alpha)}{2 \om_{k j} } C_j$$ annihilate the entry $k k$ and the submatrix becomes $${\begin{array}{c} \ell \\ k \\ j \\ i \end{array} \left[ \begin{array}{cccc} \delta_{\ell} + \alpha & 0 & & \\ 0& 0 & \om_{ k j} & 0 \\ & \om_{ j k} & 0 & \\ & 0& & a(v_i) \end{array} \right]}.$$ Finally, the operations $$ \begin{array}{cccccc} R_j & \leftarrow & R_j + \frac{1}{\om_{ k j}} R_k , & C_j & \leftarrow & C_j + \frac{1}{\om_{ j k}} C_k ,\\ &&&&&\\ R_k & \leftarrow & R_k - \frac{\om_{ k j}}{2 } R_j , & C_k & \leftarrow & C_k - \frac{\om_{ j k }}{2 } C_j \end{array} $$ yield the diagonalized form $$ {\begin{array}{c} \ell \\ k \\ j \\ i \end{array} \left[ \begin{array}{cccc} \delta_{\ell} + \alpha & 0 & & \\ 0 & -\frac{(\om_{ k j})^2}{2} & 0 & 0 \\ & 0 & 2 & \\ & 0& & a(v_i) \end{array} \right]}.$$ The diagonal values of $v_j$ and $v_k$ obtained after the operations above are exactly the values directly assigned by the algorithm in Step 2. We also note that all other children of $v_k$ are unaffected by the operations above, including those that might have zero values. Considering that the diagonal values computed by algorithm $\textit{DiagonalizeW}(T, \alpha)$ were obtained by elementary row and column operations, such that each operation performed in one row was also performed in the corresponding column, it follows that the diagonal matrix $D_{\alpha}$, whose entries are the diagonal values assigned by the algorithm, is congruent to $\Lp(T) + \alpha I$. Therefore, by Sylvester's Law of Inertia (see \cite[Theorem 4.5.8]{horn}), we have the next result. \begin{thmTEMA} \label{mainA} Given a real diagonal matrix $D$, let $D_{\alpha}$ be the diagonal matrix produced by the algorithm $ \textit{DiagonalizeW}(T, -\alpha)$ for a weighted tree $T$ and real number $\alpha$. Then, the number of positive, negative and zero diagonal entries in $D_{\alpha}$ is equal to the number of eigenvalues of the perturbed Laplacian matrix of $T$ with respect to $D$, $\Lp(T)$, which are greater, smaller and equal to $\alpha$, respectively. \end{thmTEMA} \begin{example} Let $T$ be the weighted tree with vertices $v_1, v_2, v_3, v_4$ and $ v_5$ on the left side of \mbox{Figure \ref{fig3}}, with weights represented on the edges. Suppose that the diagonal entries of matrix $D$ are $\delta_1 = 1, \, \delta_2 = 2, \, \delta_3 = 1, \, \delta_4 = 1$ and $\delta_5 = 1$. Let us apply algorithm \textit{DiagonalizeW}$(T, \alpha)$, with $ \alpha = -2 $. The initial diagonal values assigned to the vertices are $a(v_i) = \delta_{i} - 2$, for $i=1,...,5$, which are represented on the vertices of $T$, on the left side of Figure \ref{fig3}. \begin{figure}[h!] \centering \fbox{\includegraphics[width=10cm, height=9cm, keepaspectratio=true]{figura3.jpg}} \caption{Algorithm $\textit{DiagonalizeW}(T, \alpha)$ with $\alpha =-2$.} \label{fig3} \end{figure} Vertices $v_4$ and $v_5$ are the children of $v_3$ and have nonzero values, hence the algorithm assigns $a(v_3)\,\, =\,\, - 1 - \frac{(\om_{34})^2}{a(v_4)} - \frac{(\om_{35})^2}{ a(v_5)} \,\, = \,\, -1 - \frac{2^2}{-1 } - \frac{1^2}{-1}\,\, =\,\, 4.$ Vertex $v_1$ has a child with a zero value (vertex $ v_2 $), then the algorithm assigns value $2$ to $v_2$, whereas the diagonal value of $v_1$ becomes $a(v_1) \,\, = \,\, - \frac{(\om_{12})^2}{2} \,\, = \,\, - \frac{1^{2}}{2} \,\, = \,\, - \frac{1}{2}.$ Therefore, since the algorithm produced two positive and three negative diagonal values, it follows from Theorem \ref{mainA} that the matrix $ \Lp(T) $ has two eigenvalues greater than $2$ and three eigenvalues smaller than $2$. Applying the algorithm with $\alpha = 0$, we obtain that $\Lp(T) $ has one negative and four positive eigenvalues, while with $\alpha = -1$ we get that $ \Lp(T)$ has one eigenvalue equal to $1$, two eigenvalues smaller than $1$ and two eigenvalues greater than $1$. Hence, $\Lp(T)$ has one negative eigenvalue, one eigenvalue in the interval $(0, 1)$, one eigenvalue equal to $1$ and two eigenvalues greater than $2$. \end{example} \newsec{ Trees with at most five distinct eigenvalues with respect a family of Perturbed Laplacian matrices} \label{application} In this section we apply Algorithm $\textit{DiagonalizeW}(T, \alpha)$ to study trees that have up to $5$ distinct perturbed Laplacian eigenvalues. We show first that we only need to consider trees with a small diameter. We recall that the \textit{diameter} of a graph is the maximum distance between any two vertices in the graph. It is known that if $G$ is a connected graph with diameter $d$ and $M =(m_{ij})$ is a nonnegative symmetric matrix with rows and columns indexed by the vertices of $G$ and such that for distinct vertices $v_i, v_j$ we have $m_{i j} > 0$ if and only if $v_i$ and $v_j$ are adjacent, then $G$ has at least $d+1$ distinct eigenvalues with respect to $M$ (see \cite[Proposition 1.3.3]{brouwer}). We show next that this result is more general. \begin{thmTEMA} \label{diameter} If $G$ is a connected graph with positive weights and diameter $d$, then any perturbed Laplacian matrix of $G$ has at least $d+1$ distinct eigenvalues. \end{thmTEMA} \begin{proof} Let $G$ be a connected graph with order $n$, positive weights and diameter $d$. Let $\Lp(G) = D - A$ be the perturbed Laplacian matrix of $G$ with respect to a diagonal matrix $D = (d_{ij})$. Let us denote the entries of the adjacency matrix of $G$ by $a_{i j}$, with $i, j \in\{1,...,n\}$. Let $m = 1 + \underset{1 \leq k \leq n}{\max}\left\{ \lambda_k \right\}$, where $\lambda_1, \ldots, \lambda_n$ are the eigenvalues of $\Lp(G)$, and consider the matrix $B = m I - \Lp(G) = mI - D + A$. Then, for all $i, j\in \{1,...,n\}$ with $i\neq j$, $b_{i j} = a_{i j} \geq 0$. Besides, for all $i\in \{1,...,n\}$, the diagonal entry $b_{i i} = m - d_{ii}$ of $B$ is positive. This follows from the fact that $\Lp(G)$ is symmetric and then, by Schur's Theorem \cite[Theorem 4.3.45]{horn}, $d_{i i } \leq \underset{1 \leq k \leq n}{\max}\left\{ \lambda_k \right\} < m$. Therefore, by \cite[Proposition 1.3.3]{brouwer}, $B$ has at least $d +1$ distinct eigenvalues. Since the eigenvalues of $B$ are $ m - \lambda_1, \ldots, m - \lambda_n$, it follows that $\Lp(G)$ has at least $d +1$ distinct eigenvalues. \end{proof} The perturbed Laplacian matrix of a graph depends on an arbitrary diagonal matrix $D$. We consider the case where $D = \mu I$, for some $ \mu \in \mathbb{R} $, thus the perturbed Laplacian matrix of a graph $G$ is of the form $$ \Lp (G) =\mu I - A. $$ Note that, in particular, if $\mu = 0 $, $ \Lp(G) = - A$. Besides, if $G$ has no isolated vertices, $ \mu = 1 $ and the weights of $G$ are $ \omega_ {ij} = \frac{1}{\sqrt {d_i d_j}},$ then $\Lp(G)$ is the normalized Laplacian matrix of $G'$, where $G'$ is an unweighted graph with the same edges and vertices then $G$. Hence the adjacency matrix of a weighted graph and the normalized Laplacian matrix of an unweighted graph with no isolated vertices are special cases of a perturbed Laplacian matrix of the form $\Lp (G) = \mu I - A$. It is known that the spectrum of the adjacency matrix of a connected graph $G$ is symmetric if and only if $G$ is bipartite (see \cite[Proposition 3.4.1] {brouwer}). The family of perturbed Laplacian matrices that we are considering satisfies a similar result. It is easy to see that the spectrum of $ \mu I - A $ is symmetric about $\mu \in \mathbb{R}$ if and only if the spectrum of $A$ is symmetric. In fact, if $ \lambda $ is an eigenvalue of $\mu I - A$, then $ \mu - \lambda $ is an eigenvalue of $ A$. Hence, if the spectrum of $ A $ is symmetric, then $ \lambda - \mu $ is also an eigenvalue of $ A $. Thus, $\mu - (\lambda - \mu) = 2\mu - \lambda $ is an eigenvalue of $ \mu I - A $. The converse is similar. \begin{thmTEMA} \label{symmetric} Let $G$ be a connected weighted graph of order $n$ and $\mu \in \mathbb{R}$. Then $G$ is bipartite if and only if the spectrum of $\Lp (G)= \mu I - A $ is symmetric about $\mu$. \end{thmTEMA} In order to characterize the trees that have at most five distinct eigenvalues for perturbed Laplacian matrices of the form $ \mu I - A $, for some $ \mu \in \mathbb{R} $, by Theorem \ref{diameter} it is enough to consider trees with diameter smaller than five, since every tree is a connected graph. Besides, every tree $T$ is a bipartite graph, so the spectrum of $\Lp (T)= \mu I - A $ is symmetric about $\mu$. Let $T$ be a tree with $n$ vertices and diameter $d$ less than or equal to $4$. If $ d = 1 $, $ T $ is the complete graph with two vertices and has two different eigenvalues: $\mu + \omega$ and $\mu - \omega$, where $\omega$ is the weight of the edge that connects the vertices. In the case $d = 2$, $T$ is the star $S_n$, that has exactly three distinct eigenvalues, symmetric about $ \mu $, which is an eigenvalue with multiplicity to $n-2$. To see that, we apply algorithm $\textit{DiagonalizeW}(S_n, \alpha)$, with $ \alpha = - \mu $ and the vertex with degree $n-1$ as the root. Since all $n-1$ pendants of $S_n$ receive zero diagonal values, the algorithm assigns to the root $v$ the diagonal value $-\frac{(\omega_{v y^{{}*{}}})^2}{2}$, where $y^{{}*{}}$ is a pendant of $v$ selected to receive value $2$. Therefore, exactly $n-2$ vertices have a zero diagonal value at the end of the execution, which implies that $ \mu $ is an eigenvalue with multiplicity to $n-2$, by Theorem \ref{mainA}. Now we consider the case $d=3$. Note that any diameter 3 tree can be seen as two stars $S_{k+1}$ and $S_{\ell +1}$, where $ k, \ell \geq 1 $, with an edge linking their centers, as illustrated in Figure \ref{d3}. \begin{figure}[h!] \begin{center} \fbox{\includegraphics[width=5.5cm, height=3cm, keepaspectratio=true]{diametro3nova.jpg}} \caption{ \label{d3} A diameter 3 tree.} \end{center} \end{figure} Applying algorithm \textit{DiagonalizeW}, we obtain the following result. \begin{thmTEMA} \label{diam3} Let $T$ be a diameter $ 3 $ tree. Then all eigenvalues of $\Lp(T) = \mu I - A$, except possibly for $ \mu $, are simple. Moreover, $\Lp(T)$ has exactly four eigenvalues if and only if $ T = P_4 $, the path with four vertices. Otherwise, $ \Lp(T)$ has exactly five distinct eigenvalues. \end{thmTEMA} \begin{proof} Let $T$ be a diameter $ 3 $ tree with $ n = k + \ell + 2$ vertices, as shown in Figure \ref{d3}. By Theorem \ref{diameter}, $\Lp(T) = \mu I - A$ has at least four distinct eigenvalues. If $n = 4$, $T$ is the path $P_4$ and $\Lp(T)$ has exactly four distinct eigenvalues. Suppose that $n >4$ and let us apply the algorithm $ \textit{DiagonalizeW}(T, \alpha) $, with $ \alpha = - \mu $ and $ T $ rooted at the vertex with $ \ell $ pendants. Then all vertices are initialized with a zero value. Since all $k$ pendants of the vertex adjacent to the root have zero values, when this vertex is processed its diagonal value becomes negative and one of its $k$ pendants receives a positive value. Besides, since $ \ell \geq 1 $, the root has at least one pendant with a zero value. Hence, when the algorithm processes the root, its diagonal value becomes negative and exactly one of its $ \ell $ pendants receives a positive value. Therefore, at the end of the execution we obtain $ k + \ell - 2 = n - 4 $ zero values. By Theorem \ref{mainA}, it follows that $\mu$ is an eigenvalue of $\Lp(T)$ with multiplicity $n-4$. Then the other four eigenvalues of $\Lp(T)$ must be distinct since it has at least four distinct eigenvalues and its spectrum is symmetric about $\mu$. Hence, $\Lp(T)$ has exactly five distinct eigenvalues if $n > 4$, which concludes the proof. \end{proof} If $T$ has diameter $d=4$, then $\Lp(T)$ has at least five distinct eigenvalues. Hence, the path $P_4$ is the only tree with exactly four distinct eigenvalues. We want to characterize the trees, if any, necessarily of diameter $ 4 $, that have exactly five distinct eigenvalues for the perturbed Laplacian matrix $ \mu I - A $. Every diameter $4$ tree is of the form depicted in Figure \ref{diametro4}: it contains a vertex $v$ adjacent to $k \geq 2$ vertices $v_1,..., v_k$, where $v_i$ has degree $p_i +1$, with $p_i \geq 1 $, for $i=1,\ldots, k$, and each $v_i$ is adjacent to $p_i$ pendants, and $v$ is also possibly adjacent to $m\geq 0$ pendants. In this case, we write $T = \mathcal{T}(k, p_1, p_2,\ldots, p_k, m)$. \begin{figure}[h!] \centering \fbox{\includegraphics[width=4cm, height=4cm, keepaspectratio=true]{figura4.jpg}} \caption{{\small A diameter $4$ tree $\mathcal{T}(k, p_1, p_2,\ldots, p_k, m)$.}} \label{diametro4} \end{figure} The following result gives the multiplicity of $\mu$ as an eigenvalue of $\Lp(T)= \mu I - A$, where $T$ is a diameter $4$ tree. \begin{thmTEMA} For any diameter $4$ tree of the form $T = \mathcal{T}(k, p_1, p_2,\ldots, p_k, m)$, the multiplicity of $ \mu $ as an eigenvalue of $\mu I - A$ is $ 1 -k + \sum_{i=1}^{k} p_i \, \geq 1, $ when $m = 0$, and $ m - 1 - k + \sum_{i=1}^{k} p_i , $ when $ m> 0 $. \label{multmudiam4} \end{thmTEMA} \begin{proof} Let us apply the algorithm $\mbox{\textit{DiagonalizeW}}(T, \alpha)$, with $ \alpha = - \mu $, to $T$ rooted at vertex $v$ of degree $k + m$, which is adjacent to the vertices $ v_1, v_2, \ldots, v_k $ of degree $ p_1 + 1, \dots, p_k + 1 $, respectively. Suppose that $ m = 0 $, that is, $v$ has no pendants. Since $\mu + \alpha = 0$, initially all vertices are assigned a zero diagonal value, as the left hand-side of Figure \ref{diam4m0} shows. Next, for $i=1,\ldots, k$, the value of $ v_i $ becomes $-\frac{(\omega_{v_i v_{i}^{{}*{}}})^2}{2}$, where $v_{i}^{{}*{}}$ is a pendant of $ v_i $ chosen to take value $2$, and the edge connecting $v_i$ to $v$ is removed, so that the value of the root $v$ remains $0$. The other $\sum {(p_i - 1)}$ pendants also remain with a zero diagonal value, as illustrated in the right-hand side of Figure \ref{diam4m0}. Therefore, by Theorem \ref{mainA}, the multiplicity of $ \mu $ as an eigenvalue of $\Lp(T)= \mu I - A$ is exactly $$\sum_{i=1}^{k} (p_i - 1) + 1 \, = \, \left(\sum_{i=1}^{k} p_i\right) - k + 1 \, \geq 1.$$ \begin{figure}[h!] \begin{center}$ \begin{array}{cc} \fbox{\includegraphics[width=5.5cm, height=5cm, keepaspectratio=true]{figure4dia4part1.jpg}} & \includegraphics[width=1cm, height=2cm]{arrow.jpg}\hspace{0.5cm} \fbox{\includegraphics[width=5.5cm, height=5cm, keepaspectratio=true]{figure4diam4part2.jpg}}\\ \end{array}$ \end{center} \caption{\label{diam4m0} A diameter $4$ tree with $m=0.$} \end{figure} Now suppose that $m > 0$. Figure \ref{mdifzero} illustrates the execution the algorithm in this case. All the edges connecting the $v_i$'s to $v$ are also removed. When the root $v$ is processed, since it remains connected only to its $m$ pendants, which have value 0, the value assigned to $v$ becomes $-\frac{(\omega_{v v^{{}*{}}})^2}{2}$, where $v^{{}*{}}$ is a pendant of $v$ chosen to take value $2$. Hence, by Theorem \ref{mainA}, the multiplicity of $\mu$ as an eigenvalue of $\Lp(T)= \mu I - A$ is $$\left(\sum_{i=1}^{k} p_i \right)- k + (m-1).$$ \begin{figure}[h!] \begin{center}$ \begin{array}{cc} \fbox{\includegraphics[width=5.5cm, height=5cm, keepaspectratio=true]{figure5dia4part1.jpg}} & \includegraphics[width=1cm, height=2.5cm]{arrow.jpg}\hspace{0.5cm} \fbox{\includegraphics[width=5.5cm, height=5cm, keepaspectratio=true]{figure5diam4part2.jpg}}\\ \end{array}$ \end{center} \caption{\label{mdifzero} A diameter $4$ tree with $m\neq 0$.} \end{figure} \end{proof} The next result gives the multiplicity of the eigenvalues of $\Lp(T) = \mu I - A$ that are different from $\mu$ for a diameter $4$ tree $T$. Let $\omega_{i h}$ be the weight of the edge that connects $v_i$ to its pendant $q_{i h}$, for $i=1,..., k$ and $h = 1, ..., p_i$. \begin{thmTEMA} Let $T=\mathcal{T}(k, p_1, p_2,\ldots, p_k, m)$ be a diameter $4$ tree. Then $\Lp(T) = \mu I - A$ has an eigenvalue different from $\mu$ with multiplicity $t \geq 2$ if and only if $t < k$ and exactly $t+1$ $v_i's$ have the same sum of the squares of the weights $\omega_{i h}$, $h=1,..., p_i$, of the edges that connect $v_i$ to its $p_i$ pendants. Moreover, $\lambda_1 = \mu - \sqrt{\sigma}$ and $\lambda_2= \mu + \sqrt{\sigma}$ are eigenvalues of $\Lp(T)= \mu I - A $ with multiplicity $t \geq 1$ if $\displaystyle\sum_{h = 1}^{p_i} (\omega_{i h})^2 = \sigma$ for exactly $t+1$ $v_i's$. \label{multnotmu} \end{thmTEMA} \begin{proof} Let us suppose that $\lambda \neq \mu $ is an eigenvalue of $\Lp(T)$ with multiplicity $t \geq 2$. Applying algorithm $\textit{DiagonalizeW}(T, - \lambda)$ to $T$ rooted at vertex $v$ of degree $k+m$, each pendant of $T$ receives the initial diagonal value $\mu - \lambda \neq 0$. Hence, $ a(v_i) = \mu - \lambda - \displaystyle\sum_{h = 1}^{p_i} \frac{(\omega_{i h})^2}{\mu-\lambda }$, for all $1\leq i \leq k$. Due to the multiplicity of $\lambda$, the algorithm produces exactly $t$ zero diagonal values. Considering that each pendant of $T$ has a nonzero diagonal value and $t \geq 2$, then $a(v_i) = 0$ for at least one $i$, since otherwise the only possible zero diagonal value would be $a(v)$, which contradicts the fact that $t \geq 2$. Thus, the only way to obtain exactly $t$ zero diagonal values at the end of the algorithm is that $a(v_i)=0$ for exactly $t+1$ $v_i$'s, so that, after processing vertex $v$, the diagonal value of $v$ is negative and one of those $t+1$ $v_i$'s has a positive diagonal value. This implies that $t+1 \leq k$. Besides, for $1 \leq i < j \leq k$, $$a(v_i) = a(v_j) \Leftrightarrow \mu - \lambda - \sum_{h = 1}^{p_i} \frac{(\omega_{i h})^2}{\mu-\lambda }= \mu - \lambda - \sum_{h = 1}^{p_j} \frac{(\omega_{j h})^2}{\mu-\lambda } \Leftrightarrow \sum_{h = 1}^{p_i} (\omega_{i h})^2 = \sum_{h = 1}^{p_j} (\omega_{i j})^2.$$ Without loss of generality, now let us suppose that for some $t$, $1 \leq t < k$, there exists $\sigma \in \R$ such that $\displaystyle\sum_{h = 1}^{p_i} (\omega_{i h})^2 = \sigma$, for all $i$, \, $1\leq i \leq t+1$, and $\displaystyle\sum_{h = 1}^{p_i} (\omega_{i h})^2 \neq \sigma$, for $i > t+1$. We apply algorithm $\textit{DiagonalizeW}(T, \alpha)$ to $T$ rooted at vertex $v$ of degree $k+m$ and $\alpha=-\lambda$, where $\lambda = \mu - \sqrt{\sigma}$. Initially all pendants of $T$ are assigned a diagonal value $\mu -\lambda = \sqrt{\sigma} $, which is positive. Besides, for each $i$, $1\leq i \leq t+1$, $v_i$ is assigned a zero value, since \[ a(v_i) = \mu - \lambda - \sum_{h = 1}^{p_i} \frac{(\omega_{i h})^2}{\mu-\lambda } = \frac{(\mu - \lambda)^2 - \sigma }{\mu -\lambda} = 0. \] Therefore, when vertex $v$ is processed, we obtain $a(v_j) = 2$, for exactly one $j$ in $\{1,\ldots, t+1\}$ and $a(v) = -\frac{(\omega_{v v_j})^2}{2} < 0$. Hence, at the end of the execution, there are exactly $t$ zero diagonal values, which implies that $\lambda$ is an eigenvalue of $\Lp(T)$ with multiplicity $t$. The result for $\lambda = \mu + \sqrt{\sigma}$ follows from the symmetry of the spectrum of $\Lp(T) = \mu I - A$ with respect to $\mu$ (Theorem \ref{symmetric}). \end{proof} \begin{coroTEMAi} \label{distinct} If $\displaystyle\sum_{h = 1}^{p_i} (\omega_{i h})^2 \neq \sum_{h = 1}^{p_j} (\omega_{j h})^2,$ for all $ 1 \leq i < j \leq k$, then, except possibly by $\mu$, all eigenvalues of $\Lp(T) = \mu I - A$ are simple. \end{coroTEMAi} The result below characterizes the diameter $4$ trees for which the perturbed Laplacian matrix of the form $\mu I - A$ has exactly $5$ distinct eigenvalues. \begin{thmTEMA} \label{mzero} Let $T = \mathcal{T}(k, p_1, p_2,\ldots, p_k, m)$ be a diameter $4$ tree . If $m=0$ and $k = 2$, or $m = 0$, $k \geq 3$ and for all $i=1,...,k$, the vertices $v_i$ adjacent to the vertex of degree $k+m$ have the same sum of the squares of the weights $\omega_{i h}$, $h=1,..., p_i$, of the edges that connect $v_i$ to its pendants, then $\Lp(T) = \mu I - A$ has exactly $5$ distinct eigenvalues. Otherwise, $\Lp(T)$ has at least $6$ distinct eigenvalues. \end{thmTEMA} \begin{proof} If $m =0$, then, by Theorem \ref{multmudiam4}, the multiplicity of $\mu$ as an eigenvalue of $\Lp(T) = \mu I - A$ is $ 1 - k + \displaystyle \sum_{i=1}^{k} p_i \geq 1$. Hence, $\Lp(T)$ has exactly $2k$ eigenvalues different from $\mu$. If $k =2$, the result is clear, since $T$ has at least $5$ distinct eigenvalues by Theorem \ref{diameter}. Let us suppose that $k \geq 3$. If $\displaystyle \sum_{h = 1}^{p_i} (\omega_{i h})^2 = \sigma,$ for all $ 1 \leq i \leq k$, by Theorem \ref{multnotmu}, $\lambda_1 = \mu +\sqrt{\sigma} $ and $\lambda_2 = \mu - \sqrt{\sigma} $ are eigenvalues of $\Lp(T)$ with multiplicity $k - 1 \geq 1$. Hence $\Lp(T)$ has $ 2k -( 2(k-1 ) ) = 2$ eigenvalues different from $\mu$, $\lambda_1$ and $\lambda_2$. These two eigenvalues are simple, since the spectrum of $\Lp(T)$ is symmetric about $\mu$ (Theorem \ref{symmetric}), which shows that $\Lp(T)$ has exactly $5$ distinct eigenvalues. However, if $\displaystyle\sum_{h = 1}^{p_i} (\omega_{i h})^2 = \sigma$, for all $1 \leq i \leq t$, for some $2 \leq t < k$, and $\displaystyle\sum_{h = 1}^{p_i} (\omega_{i h})^2 \neq \sigma$, for all $i > t$, the multiplicity of $\lambda_1 $ and $\lambda_2$ is $t-1$. Hence $\Lp(T)$ has $2(k - t + 1) \geq 4$ eigenvalues different from $\mu$, $\lambda_1$ and $\lambda_2$, which implies that $\Lp(T)$ has at least $7$ distinct eigenvalues. If $\displaystyle \sum_{h = 1}^{p_i} (\omega_{i h})^2 \neq \sum_{h = 1}^{p_j} (\omega_{j h})^2,$ for all $ 1 \leq i < j \leq k$, by Corollary \ref{distinct}, $\Lp(T)$ has $2 k \geq 6$ simple eigenvalues different from $\mu$, which shows that $\Lp(T)$ has at least $7$ distinct eigenvalues. Finally, if $ m >0$ and $k \geq 2$, by Theorem \ref{multmudiam4}, the multiplicity of $\mu$ is $m -1 - k + \displaystyle\sum_{i=1}^{k} p_i \geq 0$ and $\Lp(T)$ has $ 2k+2 \geq 6$ eigenvalues different from $\mu$. By Theorems \ref{symmetric} and \ref{multnotmu}, it follows that $\Lp(T)$ has at least $6$ distinct eigenvalues, since in this case the multiplicity of $\mu$ can be zero. \end{proof} \begin{abstract} {\bf Resumo}. Nós apresentamos um algoritmo de tempo linear para calcular o número de autovalores de uma matriz laplaciana perturbada qualquer associada a uma árvore, num dado intervalo real. Este algoritmo pode ser aplicado a árvores com ou sem pesos. Utilizando este procedimento, obtemos uma caracterização das árvores com até cinco autovalores distintos para uma família de matrizes laplacianas perturbadas, que inclui a matriz de adjacências e a matriz laplaciana normalizada como casos particulares, entre outras. \end{abstract} %%%%%%%%%%%%%%%%% \begin{thebibliography}{00} \bibitem{Bap01} R.B. Bapat, S. J. Kirkland, S. Pati, The perturbed Laplacian matrix of a graph, {\em Linear and Multilinear Algebra}, {\bf 49} (2001), 219--242. \bibitem{brouwer} A.E. Brouwer, W.H. Haemers, ``Spectra of graphs'', Springer, New York, 2012. %(http://homepages.cwi.nl/~aeb/math/ipm/). \bibitem{autor} Autor, 2015. %\bibitem{braga2} R.O. Braga, R.R. Del-Vecchio, V.M. Rodrigues, V. Trevisan, Trees with 4 or 5 distinct normalized Laplacian eigenvalues, {\em Linear Algebra and its Applications}, {\bf 471} (2015), 615--635. \bibitem{chung} F.R.K. Chung, ``Spectral Graph Theory'', American Math. Soc., Providence, 1997. \bibitem{Fri11} E. Fritscher, C. Hoppen, I. Rocha, V. Trevisan, On the sum of the Laplacian eigenvalues of a tree, {\em Linear Algebra and its Applications}, {\bf 435} (2011), 371--399. \bibitem{horn} R. Horn, C.R. Johnson, ``Matrix Analysis'', Cambridge University Press, 1985. \bibitem{Jac11} D.P. Jacobs, V. Trevisan, Locating the eigenvalues of trees, {\em Linear Algebra and its Applications}, {\bf 434} (2011), 81--88. \bibitem{Rad} S. Radenkovi\'{c}, I. Gutman, Total $\pi$-electron energy and Laplacian energy: how far the analogy goes?, {\em Journal of the Serbian Chemical Society}, {\bf 73} (2007), 1343--1350. \end{thebibliography} \end{document} \newpage $ \ \ $ \thispagestyle{myheadings} \markboth{ }{ }