Bulletin T.CXXXVII de l’Académie serbe des sciences et des arts − 2008 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 33

SPECTRA OF COPIES OF BETHE TREES ATTACHED TO PATH AND APPLICATIONS

MARÍA ROBBIANO, I. GUTMAN, R. JIMÉNEZ, B. SAN MARTÍN

(Presented at the 1st Meeting, held on February 29, 2008)

A b s t r a c t. The Bethe tree B_{d,k} is the rooted tree of k levels whose root vertex has degree d, the vertices from level 2 to level k −1 have degree d+1 , and the vertices at level k have degree 1. This paper gives a decomposition of the characteristic polynomial of the adjacency matrix of the tree T (d, k, r) , obtained by attaching copies of B(d, k) to the vertices of the r-vertex path. Moreover, lower and upper bounds for the energy of T (d, k, r) are obtained.

AMS Mathematics Subject Classification (2000): 05C50

Key Words: spectrum (of graph), energy (of graph), Bethe tree

1. Introduction

Let G be a simple graph on n vertices. If we label its vertices by 1, …, n, then its adjacency matrix is given by A(G) = (a_{i,j}) , where a_{i,j} = 1 if the vertex i is connected, by an edge of G, to the vertex j, and a_{i,j} = 0 otherwise. The characteristic polynomial of A(G) is known as the characteristic polynomial of the graph G. The eigenvalues of A(G) , same as the zeros of the characteristic polynomial, form the spectrum of G [1]. The eigenvalues of G are denoted by λ_{j} = λ_{j}(G) , j = 1, …, n, and labelled so that

λ_{1} ≤ ⋯ ≤ λ_{n} .

The concept of the energy of G, defined as

E(G) = ∑_{j=1}^{n} |λ_{j}|

was introduced by one of the present authors (see [5, 6] and the references cited therein). Nikiforov [10] defines the energy of a matrix M (square or not) as the sum of its singular values. Recall that if M is a symmetric matrix, then its singular values and the moduli of its eigenvalues coincide.

Let k > 1 . A generalized Bethe tree B_{k} of k levels [13] is a rooted tree in which vertices at same level have the same degree. For j = 1, … k, we denote by d_{k−j+1} and by n_{k−j+1} the degree of the vertices at the level j and their number, respectively. Thus, d_{1} = 1 is the degree of the vertices at the level k (pendent vertices) and d_{k} is the degree of the root vertex. On the other hand, it is n_{k} = 1 , pertaining to the single vertex at the first level, the root vertex. The ordinary Bethe tree B_{d,k} is the rooted trees of k levels whose root vertex has degree d, the vertices from levels 2 to k − 1 have degree d + 1 , and the vertices at level k have degree 1 .

Spectral properties of Bethe trees (both ordinary and generalized) were much studied in the past. Heilmann and Lieb [7] have determined the decomposition of the matching polynomial of B_{d,k}. Recall that the matching and characteristic polynomials of trees coincide [2].

Other spectral properties of Bethe and similar trees were considered in [4, 12, 14, 15]. Eventually, Rojo and one of the present authors found explicit formulas for the eigenvalues of the Bethe trees [16]. With these results the authors in [11] obtained an explicit formula for the energy of the Bethe tree B_{d,k}.

Let P_{r} and C_{r} be, respectively, the r-vertex path and the r-vertex cycle. In the paper [13] the spectrum of the graph obtained by attaching copies of B_{d,k} to the vertices of C_{r} was determined. In this paper we obtain an analogous decomposition of the characteristic polynomial of the tree T (d, k, r) , obtained by attaching copies of B_{d,k} to the vertices of P_{r}. Using this result, lower and upper bounds for the energy of T (d, k, r) are established.

The tree T (2, 4, 3) is depicted in Fig. 1.

Fig. 1. The tree T (2, 4, 3)

In connection with the graphs considered in [13] and in this article, one needs to recall the following result of Godsil and McKay [3].

Denote by ϕ(H, x) the characteristic polynomial of a graph H. Let G be a graph on n vertices. Let R be a rooted graph and v its root. Construct the graph product G[R] by attaching a copy of R, via its root, to each vertex of G.

Then ϕ(G[R], x) , the characteristic polynomial of G[R] , is equal to

ϕ(R − v, x)^{n} ϕ (G, \frac{ϕ(R, x)}{ϕ(R − v, x)}) .  (1)

Evidently, the above formula is applicable to the trees T (d, k, r) . Some of the results of the present paper could have been obtained by using the Godsil–McKay formula. Yet, our reasoning follows a somewhat different path.

The present paper has five sections. In this section we recall some results from Matrix Theory. The main result in the second section is

Theorem 1. The characteristic polynomial of the tree T = T (d, k, r) has the following decomposition:

det(λ I − A(T)) = ( ∏_{j∈Ω} Q_{j}^{n_{j}−n_{j+1}}(λ))^{r} (∏_{ℓ=1}^{r} Q_{ℓ,k}(λ))  (2)

where Q_{ℓ,k}(λ) , ℓ = 1, …, r, is the characteristic polynomial of the matrix T_{ℓ,k} in Eq. (12), whereas Q_{j}(λ) , j = 1, …, k − 1 , is the characteristic polynomial of the j × j leading principal submatrix of T_{ℓ,k}.

In the third section, as an application of Theorem 1, we show that the energy of the tree T (d, 2, r) is equal to

4 ∑_{ℓ=1}^{⌊r/2⌋} \sqrt{d + cos^{2} \frac{ℓπ}{r + 1}} if r is even  (3)

2\sqrt{d} + 4 ∑_{ℓ=1}^{⌊r/2⌋} \sqrt{d + cos^{2} \frac{ℓπ}{r + 1}} if r is odd .  (4)

We denote by E(N) the energy of any matrix N . Let M = M(α, h) be the k × k tridiagonal symmetric matrix, specified

in Eq. (17). In an earlier work [11] we proved the following

Theorem 2. The energy of M(α, 0) is equal to

E(M(α, 0)) = 2α (\frac{sin(⌊k/2⌋ + 1/2)\frac{π}{k+1}}{sin \frac{π}{2(k+1)}} − 1) .

In the fourth section we obtain lower and upper bounds for the energy of a M = M(α, h) , for α > 0 , h ≥ 0 .

Let α, h > 0 . Let k ≥ 3 . Let b := b(k) be defined by

b := \frac{sin(⌊k/2⌋ + 1/2)\frac{π}{k}}{sin \frac{π}{2k}} − 1 .  (5)

We denote by B(μ) an upper bound for the greatest eigenvalue μ of the matrix M(α, h) .

Theorem 3. The energy E(M(α, h)) of the matrix M(α, h) , defined via Eq. (17), is bounded by

−2α cos \frac{π}{k} < E(M(α, h)) − 2α (b + cos \frac{π}{k + 1}) < B(μ)

whenever k is even and

−2α cos \frac{π}{k} < E(M(α, h)) − 2α (b + cos \frac{π}{k + 1}) < B(μ) − 2α cos \frac{⌊k/2⌋π}{k}

whenever k is odd, where b is given by Eq. (5).

Finally, in the last section we search for an upper bound B(μ) . We prove

Theorem 4. Let α, h > 0 . The greatest eigenvalue μ of the matrix M(α, h) , defined via Eq. (17), is bounded by B(μ) = min{B_{1}(μ), B_{2}(μ)}, where

B_{1}(μ) = max \{2α cos \frac{π}{2k + 1}, 2h cos \frac{π}{2k + 1}\} and B_{2}(μ) = max\{2α, α+h\} .

In the fifth section we also obtain lower and upper bounds for the energy of the tree T (d, k, r) .

* * * *

We recall that the Kronecker product A ⊗ B of a pair of matrices A = (a_{i,j}) and B = (b_{i,j}) of orders r × s and p × q, respectively, is the rp × sq matrix, defined by [9]

A ⊗ B = ( \begin{matrix}a_{11}B & … & a_{1s}B \\ ⋮ & ... & ⋮ \\ a_{r1}B & … & a_{rs}B \end{matrix} ) .

This binary operation has the following properties:

1. (A ⊗ B)^{T} = A^{T} ⊗ B^{T} .

2. (A ⊗ B)^{−1} = A^{−1} ⊗ B^{−1} provided that the matrices A^{−1} and B^{−1} exist.

3. (A ⊗ B)(C ⊗ D) = (AC ⊗ BD) provided that the products AC and BD exist.

4. (I_{r} ⊗ I_{s}) = I_{rs}, where for a positive integer ℓ, I_{ℓ} denotes the identity matrix of order ℓ.

5. (I_{r} ⊗ B) = diag(B, …, B) .

We denote by λ_{p}(N) the p−th eigenvalue of any matrix N and we recall the following Lemmas.

Lemma 5 (Monotonicity Theorem) [8]. Let A, B be k × k real and symmetric matrices. Let

C = A + B

and let λ_{1}(A) ≤ λ_{2}(A) ≤ ⋯ ≤ λ_{k}(A) , λ_{1}(B) ≤ λ_{2}(B) ≤ ⋯ ≤ λ_{k}(B) , and λ_{1}(C) ≤ λ_{2}(C) ≤ ⋯ ≤ λ_{k}(C) be the ordered eigenvalues of A, B, and C, respectively. Then

λ_{j}(A) + λ_{i−j+1}(B) ≤ λ_{i}(C)

whenever i ≥ j and

λ_{i}(C) ≤ λ_{j}(A) + λ_{i−j+k}(B)

whenever i ≤ j.

Lemma 6. (Interlacing Cauchy Theorem) [8]. Let

A = [ \begin{matrix}B & C \\ C^{T} & D \end{matrix} ]

be a k × k symmetric matrix, where B is a j × j principal submatrix of A. Let λ_{1}(A) ≤ λ_{2}(A) ≤ ⋯ ≤ λ_{k}(A) , λ_{1}(B) ≤ ⋯ ≤ λ_{j}(B) be the ordered eigenvalues of A and B respectively. Then for ℓ = 1, … j,

λ_{ℓ}(A) ≤ λ_{ℓ}(B) ≤ λ_{ℓ+k−j}(A) .

Lemma 7. Let A be an m × m symmetric tridiagonal matrix with nonzero codiagonal entries. Then the eigenvalues of any (m − 1) × (m − 1) principal submatrix strictly interlace the eigenvalues of A.

The following result is known as the three–term recursion formula for tridiagonal symmetric matrices. The characteristic polynomials, Q̃_{j}(λ) , of the j × j leading principal submatrices of the symmetric tridiagonal matrix

A_{k} = [ \begin{matrix}a_{1} & b_{1} \\ b_{1} & ... & ... \\ & ... & ... & b_{k−1} \\ & & b_{k−1} & a_{k} \end{matrix} ]

satisfy the following three–term recursion formula

Q̃_{j}(λ) = (λ − a_{j})Q̃_{j−1}(λ) − b_{j−1}^{2}Q̃_{j−2}(λ) , j = 2, …, k  (6)

where

Q̃_{0}(λ) = 1  and  Q̃_{1}(λ) = λ − a_{1} .

Let L > 0 . In [11] it was shown that

∑_{k=1}^{n} (2 cos \frac{kπ}{L} ) = \frac{sin(n + 1/2)\frac{π}{L}}{sin \frac{π}{2L}} − 1 .  (7)

2. Characteristic polynomial of T (d, k, r)

We observe that on the level j, j = 1, …, k of the tree T := T (d, k, r) , there are r n_{k−j+1} vertices. Hence and if n denotes the order of adjacency

matrix, we see that n = r ∑_{j=1}^{k} n_{j} .

From our notation for the tree B_{k} it is clear that

n_{k−j} = (d_{k−j+1} − 1)n_{k−j+1} , j = 1, …, k − 1  and  n_{k−1} = d_{k} .

Here and in what follows 0 denotes the all–zero matrix; its order is clear from the context. For a positive integer ℓ let e_{ℓ} = (1, …, 1)^{T} , the all–one vector of order ℓ. Let

m_{j} = \frac{n_{j}}{n_{j+1}} , j = 1, …, k − 1 .

Hence,

m_{j} = d_{j+1} − 1 , j = 1, …, k − 2

and

m_{k−1} = d_{k} .

Let B_{j} be the block diagonal matrix defined by

B_{j} = I_{n_{j+1}} ⊗ e_{m_{j}}

with n_{j+1} diagonal blocks equal to e_{m_{j}} . We observe that B_{j} has order n_{j} × n_{j+1} and that B_{k−1} = e_{n_{k−1}} . For j = 1, …, k − 1 , let C_{j} be the (r n_{j}) × (r n_{j+1}) block diagonal matrix,

C_{j} = I_{r} ⊗ B_{j}

with r diagonal blocks equal to B_{j} . Hence C_{k−1} is the r n_{k−1} × r block diagonal matrix C_{k−1} = I_{r} ⊗ e_{n_{k−1}} , with r diagonal blocks equal to e_{n_{k−1}} .

Consider the tridiagonal symmetric r × r matrices

F_{r} = [ \begin{matrix}0 & 1 \\ 1 & ... & ... \\ & ... & ... & 1 \\ & & 1 & 0 \end{matrix} ]  (8)

and

M_{r} = α F_{r} .  (9)

Observe that F_{r} is the adjacency matrix of the path P_{r}. It is well known that [1]

λ_{ℓ}(M_{r}) = 2α cos \frac{(r + 1 − ℓ)π}{r + 1} , ℓ = 1, …, r .

Therefore, λ_{ℓ}(M_{r}) = −λ_{r+1−ℓ}(M_{r}) , ℓ = 1, …, r. Moreover if r is odd, then λ_{(r+1)/2}(M_{r}) = 0 .

In view of our labelling, the adjacency matrix of T (d, k, r) becomes equal to the following block tridiagonal matrix:

A(T (d, k, r)) = [ \begin{matrix}0 & C_{1} \\ C_{1}^{T} & ... & ... \\ & ... & 0 & C_{k−1} \\ & & C_{k−1}^{T} & F_{r} \end{matrix} ] .

Lemma 8. For j = 1, …, k, let α_{j} := α_{j}(λ) be a polynomial with real coefficients, and

M_{1} = [ \begin{matrix}α_{1} I_{r n_{1}} & −C_{1} \\ −C_{1}^{T} & ... & ... \\ & ... & α_{k−1} I_{r n_{k−1}} & −C_{k−1} \\ & & −C_{k−1}^{T} & α_{k} I_{r} − F_{r} \end{matrix} ] .

Moreover let

β_{1} = α_{1}

and β_{j−1}(λ) ≠ 0 ,

β_{j} = α_{j} − \frac{n_{j−1}}{n_{j}} \frac{1}{β_{j−1}}

for j = 2, 3, …, k. Then for all real λ, such that β_{j}(λ) ≠ 0 , j = 1, 2, …, k− 1 ,

det M_{1} = (β_{1}^{n_{1}}β_{2}^{n_{2}} ⋯ β_{k−1}^{n_{k−1}})^{r} ∏_{ℓ=1}^{r} (β_{k} − 2 cos \frac{ℓπ}{r + 1}) .  (10)

P r o o f. For the matrix M_{1} we proceed as in Gaussian elimination, but this time we use the blocks. Thus for j = 1, …, k−1 and β_{j} ≠ 0 , the matrix C_{j}^{T} is eliminated with β_{j} I_{rn_{j}} , in consequence α_{j+1} I_{r n_{j+1}} is replaced by α_{j+1} I_{r n_{j+1}} − β_{j}^{−1} C_{j}^{T} C_{j} I_{r n_{j}} . Via definition of matrices B_{j} and C_{j} and the above properties of Kronecker product, we prove directly that C_{j}^{T} C_{j} I_{r n_{j}} = m_{j} I_{r n_{j+1}} = \frac{n_{j}}{n_{j+1}} I_{r n_{j+1}} . Then

α_{j+1} I_{r n_{j+1}} − β_{j}^{−1} C_{j}^{T} C_{j} I_{r n_{j}} = β_{j+1} I_{r n_{j+1}} .

Finally this process yields the matrix

α_{k} I_{r} − F_{r} − n_{k−1} I_{r} = β_{k} I_{r} − F_{r} .

By a similar reasoning as in the Gaussian elimination, it is possible to show that the determinants of the obtained block upper triangular matrix and of M_{1} coincide. Eq. (10) follows. □

Let Ω = {j = 1, …, k − 1 : n_{j} > n_{j+1}}.

Consider the polynomials Q_{0}(λ) = 1 , Q_{1}(λ) = λ and

Q_{j}(λ) = λ Q_{j−1}(λ) − \frac{n_{j−1}}{n_{j}} Q_{j−2}(λ) , j = 2, …, k − 1 .

Finally let

Q_{ℓ,k}(λ) = (λ − 2 cos \frac{ℓπ}{r + 1}) Q_{k−1}(λ) − \frac{n_{k−1}}{n_{k}} Q_{k−2}(λ) , ℓ = 1, …, r .

Theorem 1 can now be derived from Lemma 8.

P r o o f of Theorem 1. We apply Lemma 8 to the matrix M_{1} = λ I − A(T) . For this matrix,

α_{j} = λ , j = 1, …, k .

Suppose that λ ∈ ℝ is such that Q_{j}(λ) ≠ 0 for all j = 1, …, k − 1 . We have

β_{1} = λ = \frac{Q_{1}}{Q_{0}} ≠ 0,

β_{2} = λ − \frac{1}{β_{1}} \frac{n_{1}}{n_{2}} = \frac{λ Q_{1} − \frac{n_{1}}{n_{2}} Q_{0}}{Q_{1}} = \frac{Q_{2}}{Q_{1}} ≠ 0,

…  …  …
β_{k−1} = λ − \frac{1}{β_{k−2}} \frac{n_{k−2}}{n_{k−1}} = \frac{Q_{k−1}}{Q_{k−2}} ≠ 0

β_{k} − 2 cos \frac{πℓ}{r + 1} = λ − 2 cos \frac{πℓ}{r + 1} − \frac{n_{k−1}}{n_{k}} \frac{1}{β_{k−1}}

= (λ − 2 cos \frac{πℓ}{r + 1}) − \frac{n_{k−1}}{n_{k}} \frac{Q_{k−2}}{Q_{k−1}} = \frac{Q_{ℓ,k}}{Q_{k−1}} .

From Eq. (10) we obtain

det(λ I−A(T) = ( ∏_{j=1}^{k−1} β_{j}^{n_{j}} )^{r} ∏_{ℓ=1}^{r} (β_{k} − 2 cos \frac{πℓ}{r + 1}) = ( ∏_{j∈Ω} Q_{j}^{n_{j}−n_{j+1}} )^{r} ∏_{ℓ=1}^{r} Q_{ℓ,k} .

(11)

Thus, (2) is proved for all λ ∈ ℝ, such that Q_{j}(λ) ≠ 0 , j = 1, …, k − 1 .

Suppose now that Q_{j}(λ_{0}) = 0 for some j and for some λ_{0} ∈ ℝ. Since the zeros of any nonzero polynomial are isolated, there exists a neighborhood N(λ_{0}) of λ_{0} such that Q_{ℓ}(λ) ≠ 0 for all λ ∈ N(λ_{0}) \ {λ_{0}} and for all ℓ = 1, …, k − 1 . Hence (11) is proved for all λ ∈ N(λ_{0}) \ {λ_{0}}. By continuity, taking the limit as λ → λ_{0} , we have

det(λ_{0} I − A(T)) = ( ∏_{j∈Ω} Q_{j}^{n_{j}−n_{j+1}}(λ_{0}))^{r} ∏_{ℓ=1}^{r} Q_{ℓ,k}(λ_{0}) .

Therefore (2) holds for all λ ∈ ℝ. □

For ℓ = 1, …, r, let T_{ℓ,k} be the following k × k symmetric tridiagonal matrix

[ \begin{matrix}0 & \sqrt{d_{2} − 1} \\ \sqrt{d_{2} − 1} & 0 & ... \\ & ... & ... & \sqrt{d_{k−1} − 1} \\ & & \sqrt{d_{k−1} − 1} & 0 & \sqrt{d_{k}} \\ & & & \sqrt{d_{k}} & 2 cos \frac{ℓπ}{r+1} \end{matrix} ] .  (12)

For j = 1, …, k − 1 , let T_{j} be the j × j leading principal submatrix of T_{1,k}. The following result is a direct consequence of relation (6).

Lemma 9. For j = 1, 2, …, k − 1 ,

det(λI − T_{j}) = Q_{j}(λ)  (13)

and for ℓ = 1, 2, …, r,

det(λI − T_{ℓ,k}) = Q_{ℓ,k}(λ) .  (14)

In particular, when we attach r copies of the tree B_{d,k} to the vertices of P_{r}, then the matrices in (12) (pertaining to A(T (d, k, r))) become the following irreducible matrices, [8]:

S(ℓ, k, r) = [ \begin{matrix}0 & \sqrt{d} \\ \sqrt{d} & ... & ... \\ & ... & 0 & \sqrt{d} \\ & & \sqrt{d} & 2 cos \frac{ℓπ}{r+1} \end{matrix} ] , ℓ = 1, …, r .  (15)

Moreover for j = 1, …, k − 1 , the submatrices T_{j} , are equal to the matrices S_{j} = \sqrt{d} F_{j} where the matrix F_{j} is as in (8). The energy of these matrices is given by [11]

E(S_{j}) = 2\sqrt{d} (\frac{sin(⌊j/2⌋ + 1/2)\frac{π}{j+1}}{sin \frac{π}{2(j+1)}} − 1) , j = 1, …, k − 1 .

Moreover [7],

n_{j} − n_{j+1} = d^{k−1−j} (d − 1) .  (16)

We denote by S_{k} the matrix \sqrt{d} F_{k}, where F_{k} is as in (8). For matrices in (15) we observe,

λ_{p}(S(ℓ, k, r)) = −λ_{k+1−p}(S(r + 1 − ℓ, k, r)) , p = 1, …, k , ℓ = 1, …, r .

For r ≥ 2 this property and the definition of energy imply

E(S(ℓ, k, r)) = E(S(r + 1 − ℓ, k, r)) , ℓ = 1, …, ⌊r/2⌋ .

For odd r and ℓ = 1 + ⌊r/2⌋, it is 2 cos \frac{ℓπ}{r+1} = 0 , which implies S(1 + ⌊r/2⌋, k, r) = S_{k}. Therefore we obtain [11],

E(S(1 + ⌊r/2⌋, k, r)) = 2\sqrt{d} (\frac{sin(⌊k/2⌋ + 1/2)\frac{π}{k+1}}{sin \frac{π}{2(k+1)}} − 1) .

The following Lemma is a consequence of Theorem 1 and Lemmas 5, 6 and 7.

Lemma 10. Let 1 ≤ ℓ_{1} ≤ ℓ_{2} ≤ ⌊r/2⌋. Then,

a) λ_{p}(S(ℓ_{2}, k, r)) ≤ λ_{p}(S(ℓ_{1}, k, r)) , p = 1, …, k,

b) λ_{p}(S(ℓ, k, r)) < λ_{p}(S_{j}) < λ_{p+k−j}(S(ℓ, k, r)) , p = 1, …, j , ℓ = 1, …, ⌊r/2⌋.

c) The greatest ⌊r/2⌋ eigenvalues of the tree T (d, k, r) are the greatest eigenvalues of the matrices S(ℓ, k, r) , ℓ = 1, …, ⌊r/2⌋, whenever r is an even number, and the greatest ⌊r/2⌋ + 1 eigenvalues of the tree T (d, k, r) are the greatest ⌊r/2⌋ + 1 eigenvalues of S(ℓ, k, r) , ℓ = 1, …, ⌊r/2⌋ + 1 , whenever r is an odd number.

d) The greatest eigenvalue of T (d, k, r) is λ_{k}(S(1, k, r)) .

P r o o f. Note that S(ℓ_{1}, k, r) = S(ℓ_{2}, k, r)+B, where B = [ \begin{matrix}0 & 0 \\ 0^{T} & g \end{matrix} ] ,

g > 0 . By Lemma 5 we have

λ_{q}(S(ℓ_{2}, k, r)) + λ_{p−q+1}(B) ≤ λ_{p}(S(ℓ_{1}, k, r)) , p ≥ q .

We obtain the first result by taking q = p. The second result is obtained by observing that S_{j} is a j × j submatrix of the matrix S(ℓ, k, r) and by applying Lemma 6. The facts c) and d) are obtained as consequence of the Theorem 1 and of a) and b). □

3. Example: The energy of T (d, 2, r)

In this section, in order to exemplify the general theory from the previous section, we compute the spectrum and energy of T (d, 2, r) . The same results could have been obtained also by using the Godsil–McKay formula (1). The figure below corresponds to T (2, 2, 8) .

Fig. 2. The tree T (2, 2, 8) .

Spectra of copies of Bethe trees 71

For the tree T (d, 2, r) the matrices in (15) reduce to the following 2 × 2 matrices:

S(ℓ, 2, r) = [ \begin{matrix}0 & \sqrt{d} \\ \sqrt{d} & 2 cos \frac{ℓπ}{r+1} \end{matrix} ] , ℓ = 1, …, ⌊r/2⌋

with eigenvalues

cos \frac{ℓπ}{r + 1} ± \sqrt{d + cos^{2} \frac{ℓπ}{r + 1}} , ℓ = 1, …, ⌊r/2⌋ .

All other eigenvalues of T (d, 2, r) are equal to zero. Thus

E(S(ℓ, 2, r)) = |cos \frac{ℓπ}{r + 1} + \sqrt{d + cos^{2} \frac{ℓπ}{r + 1}}| + |cos \frac{ℓπ}{r + 1} − \sqrt{d + cos^{2} \frac{ℓπ}{r + 1}}|
= 2\sqrt{d + cos^{2} \frac{ℓπ}{r + 1}} .

Then the decomposition in (2) and the matrices in (15) imply Theorem 11. The energy E(T (d, 2, r)) is given by Eqs. (3) and (4).

4. Bounds for the energy of certain matrices

Let α > 0 and h ≥ 0 . Consider the tridiagonal symmetric k × k matrix

M := M(α, h) = [ \begin{matrix}M_{k−1} & (0, 0, …, 0, α)^{T} \\ (0, 0, …, 0, α) & h \end{matrix} ]  (17)

where M_{k−1} = α F_{k−1} is given by Eq. (9). Then,

λ_{j}(M_{k−1}) = 2α cos \frac{(k − j)π}{k} , j = 1, …, k − 1 .  (18)

Lemma 12a. Let k = 2p. Then for i = 2, …, k − 1 ,

2α cos \frac{iπ}{k} < |λ_{i}(M)| < 2α cos \frac{(i − 1)π}{k} , i = 2, …, p  (19)

and

2α cos \frac{(k − i + 1)π}{k} < |λ_{i}(M)| < 2α cos \frac{(k − i)π}{k} , i = p+1, …, k−1 . (20)

P r o o f. We consider the ordered eigenvalues

λ_{1}(M) ≤ λ_{2}(M) ≤ ⋯ ≤ λ_{k}(M) .

By Lemmas 5 and 6, and by using the eigenvalues in (18), we derive,

2α cos \frac{(k − i + 1)π}{k} < λ_{i}(M) < 2α cos \frac{(k − i)π}{k} , i = 2, …, k − 1 . (21)

Hence, if i ≤ p then 2α cos \frac{(k−i)π}{k} ≤ 0 implying λ_{i}(M) < 0 . By multiplying in (21) by (−1) the inequalities in (19) are obtained. In a same way, if i ≥ p + 1 , then by 2α cos \frac{(k−i+1)π}{k} > 0 we have λ_{i}(M) ≥ 0 , and (20) follows from (21). □

Lemma 12b. Let k = 2p + 1 . Then

2α cos \frac{iπ}{k} < |λ_{i}(M)| < 2α cos \frac{(i − 1)π}{k} , i = 2, …, p  (22)
0 ≤ |λ_{p+1}(M)| < 2α cos \frac{p π}{k}  (23)

and

2α cos \frac{(k − i + 1)π}{k} < |λ_{i}(M)| < 2α cos \frac{(k − i)π}{k} , i = p+2, …, k−1 . (24)

P r o o f. As before, the inequalities (21) imply (22). For i = p + 1 in (21) we obtain

2α cos \frac{(p + 1)π}{2p + 1} < λ_{p+1}(M) < 2α cos \frac{p π}{2p + 1} .

Hence, by using the identity

cos \frac{(p + 1)π}{2p + 1} = − cos \frac{pπ}{2p + 1}

we arrive at (23). If i ≥ p + 2 , then 2α cos \frac{(k−i+1)π}{k} > 0 . Therefore, (24) follows directly from (21). □

Let b := b(k) be defined as

b := ∑_{i=1}^{⌊k/2⌋} (2 cos \frac{iπ}{k} ) = \frac{sin(⌊k/2⌋ + 1/2)\frac{π}{k}}{sin \frac{π}{2k}} − 1  (25)

where the last identity is implied by (7).

Lemma 13. Let k be an even number. Let b be as in (25). Consider the tridiagonal symmetric k × k matrix M = M(α, h) , Eq. (17), and suppose that a_{1} < |λ_{1}(M)| < b_{1} and a_{k} < |λ_{k}(M)| < b_{k}. Then

a_{1} + a_{k} − 4α cos \frac{π}{k} < E(M) − 2αb < b_{1} + b_{k} .

P r o o f. Let k = 2p. Thus ⌊k/2⌋ = p. Clearly

E(M) = |λ_{1}(M)| + |λ_{k}(M)| + ∑_{i=2}^{p} |λ_{i}(M)| + ∑_{i=p+1}^{k−1} |λ_{i}(M)| . (26)

By summation from i = 2 to i = p in the inequalities in (19) we obtain

α ∑_{i=2}^{p} 2 cos \frac{iπ}{k} < ∑_{i=2}^{p} |λ_{i}(M)| < α ∑_{i=2}^{p} 2 cos \frac{(i − 1)π}{k} .

For this case

∑_{i=2}^{p} 2 cos \frac{(i − 1)π}{k} = ∑_{i=1}^{p} 2 cos \frac{iπ}{k} = b .

Thus from the above inequalities and (25) we have

α (b − 2 cos \frac{π}{k} ) < ∑_{i=2}^{p} |λ_{i}(M)| < αb .  (27)

In (20) we take the sum from i = p + 1 , to i = k − 1 , thus obtaining

α ∑_{i=p+1}^{k−1} 2 cos \frac{(k − i + 1)π}{k} < ∑_{i=p+1}^{k−1} |λ_{i}(M)| < α ∑_{i=p+1}^{k−1} 2 cos \frac{(k − i)π}{k} . (28)

By a change of variable,

α ∑_{i=p+1}^{k−1} 2 cos \frac{(k − i + 1)π}{k} = α ∑_{j=2}^{p} 2 cos \frac{jπ}{k} = α (b − 2 cos \frac{π}{k} )

and

α ∑_{i=p+1}^{k−1} 2 cos \frac{(k − i)π}{k} = α ∑_{j=1}^{p−1} 2 cos \frac{jπ}{k} = αb .

Thus, inequalities in (28) and (25) imply

α (b − 2 cos \frac{π}{k} ) < ∑_{i=p+1}^{k−1} |λ_{i}(M)| < αb .  (29)

Now the result is obtained directly from (26), bounds in (27) and (29) and the bounds given for |λ_{1}(M)| and |λ_{k}(M)|. □

Lemma 14. Let k be an odd integer. Let b be as in (25) and M = M(α, h) as in (17). Suppose that a_{1} < |λ_{1}(M)| < b_{1} and a_{k} < |λ_{k}(M)| < b_{k}. Then

a_{1} + a_{k} − 4α cos \frac{π}{k} < E(M) − 2αb < b_{1} + b_{k} − 2α cos \frac{⌊k/2⌋π}{k} .

P r o o f. Let k = 2p + 1 . Thus ⌊k/2⌋ = p. Evidently,

E(M) = |λ_{1}(M)|+|λ_{k}(M)|+∑_{i=2}^{p} |λ_{i}(M)|+ ∑_{i=p+2}^{k−1} |λ_{i}(M)|+|λ_{p+1}(M)| . (30)

By summation from i = 2 to i = p in (22) we obtain

α ∑_{i=2}^{p} 2 cos \frac{iπ}{k} < ∑_{i=2}^{p} |λ_{i}(M)| < α ∑_{i=2}^{p} 2 cos \frac{(i − 1)π}{k} .

Hence by (25) we directly obtain,

α (b − 2 cos \frac{π}{k} ) < ∑_{i=2}^{p} |λ_{i}(M)| < α (b − 2 cos \frac{p π}{k} ) .  (31)

Spectra of copies of Bethe trees 75

By summing from i = p + 2 to i = k − 1 in (24) we have

α ∑_{i=p+2}^{k−1} 2 cos \frac{(k − i + 1)π}{k} < ∑_{i=p+2}^{k−1} |λ_{i}(M)| < α ∑_{i=p+2}^{k−1} 2 cos \frac{(k − i)π}{k} . (32)

By a change of variable,

α ∑_{i=p+2}^{k−1} 2 cos \frac{(k − i + 1)π}{k} = α ∑_{j=2}^{p} 2 cos \frac{jπ}{k} = α (b − 2 cos \frac{π}{k} )

and

α ∑_{i=p+2}^{k−1} 2 cos \frac{(k − i)π}{k} = α ∑_{j=1}^{p−1} 2 cos \frac{jπ}{k} = α (b − 2 cos \frac{p π}{k} ) .

Thus from the inequalities in (32) and by (25) we get

α (b − 2 cos \frac{π}{k} ) < ∑_{i=p+2}^{k−1} |λ_{i}(M)| < αb − 2α cos \frac{p π}{k} .  (33)

The result is directly obtained from (30), bounds in (31), (33), and (23) as well as the bounds given for |λ_{1}(M)| and |λ_{k}(M)|. □

We recall that for the extreme eigenvalues of the matrix M(α, 0) in (17),

|λ_{1}(M(α, 0))| = |λ_{k}(M(α, 0))| = 2α cos \frac{π}{k + 1} .

Lemma 15. Let h > 0 . Then

2α cos \frac{π}{k} < |λ_{1}(M(α, h))| < 2α cos \frac{π}{k + 1}  (34)

and

2α cos \frac{π}{k + 1} ≤ |λ_{k}(M(α, h))| .  (35)

P r o o f. Consider the ordered eigenvalues of M(α, h) , λ_{1}(M(α, h)) ≤ λ_{2}M(α, h)) ≤ ⋯ ≤ λ_{k}(M(α, h)) and observe that

M(α, h) = α F_{k} + B where B = [ \begin{matrix}0 & 0 \\ 0^{T} & h \end{matrix} ] .

By Lemma 5 we have

λ_{j}(αF_{k}) + λ_{i−j+1}(B) ≤ λ_{i}(M(α, h)) , i ≥ j .  (36)

In (36), i = j = 1 imply

2α cos \frac{kπ}{k + 1} + λ_{1}(B) ≤ λ_{1}(M(α, h)) .

In this case λ_{1}(B) = 0 . Therefore

2α cos \frac{kπ}{k + 1} ≤ λ_{1}(M(α, h)) .

On the other hand, by using Lemma 7 we have

λ_{1}(M(α, h)) < λ_{1}(M_{k−1}) = 2α cos \frac{(k − 1)π}{k} .

Therefore

2α cos \frac{kπ}{k + 1} ≤ λ_{1}(M(α, h)) < 2α cos \frac{(k − 1)π}{k}

and (34) is obtained by multiplying the above inequalities by (−1) . In (36) we consider i = j = k and obtain

λ_{k}(M(α, h)) ≥ λ_{k}(αF_{k}) + λ_{1}(B) = 2α cos \frac{π}{k + 1}

which leads to (35). □

Theorem 3 is now obtained as an immediate corollary of Lemmas 13, 14, and 15.

5. Estimating the energy of T (d, k, r)

P r o o f of Theorem 4. Let

P = [ \begin{matrix}F_{k−1} & (0, 0, …, 0, 1)^{T} \\ (0, 0, …, 0, 1) & 1 \end{matrix} ]

with F_{k−1} given in Eq. (8). Let υ = max{α, h}. Then M(α, h) ≤ υP . Both M(α, h) and υP are irreducible matrices. Then by comparing their spectral radii [9] we have

λ_{k}(M(α, h)) ≤ λ_{k}(υP) = 2υ cos \frac{π}{2k + 1} .

Thus B_{1}(μ) is an upper bound of μ. By the Gershgorin theorem [9], B_{2}(μ) is an other upper bound of μ. Theorem 4 follows. □

Example. For the 20 × 20 matrix M(\sqrt{2}, 2) defined by taking k = 20 in (17) we have E(M(\sqrt{2}, 2)) = 35.9051 . Our lower and upper bounds are 31.4536 and 37.6614 , respectively.

By applying Theorem 1 to the tree T (d, k, r) , the matrices in (15) are obtained. By means of the decomposition (2), and the relations (13), (14), (16), we obtain

E(T (d, k, r)) = r ∑_{j=1}^{k−1} d^{k−1−j} (d − 1)E(S_{j}) + 2 ∑_{ℓ=1}^{⌊r/2⌋} E(S(ℓ, k, r))

for r even, and

\begin{matrix}E(T (d, k, r)) = \\ r ∑_{j=1}^{k−1} d^{k−1−j} (d − 1)E(S_{j}) + ∑_{ℓ=1}^{⌊r/2⌋} 2E(S(ℓ, k, r)) + E(S(1 + ⌊r/2⌋, k, r)) \end{matrix}

for odd r. We recall that E(B_{d,k}) denotes the energy of the Bethe tree B_{d,k}. In [11] it was proven that

∑_{j=1}^{k−1} d^{k−1−j} (d − 1)E(S_{j}) = E(B_{d,k}) − E(S_{k}) .

Therefore

E(T (d, k, r)) − r E(B_{d,k}) + r E(S_{k}) = 2 ∑_{ℓ=1}^{⌊r/2⌋} E(S(ℓ, k, r))  (37)

for even r and

E(T (d, k, r)) − r E(B_{d,k}) + (r − 1)E(S_{k}) = 2 ∑_{ℓ=1}^{⌊r/2⌋} E(S(ℓ, k, r))  (38)

78 María Robbiano, I. Gutman, R. Jiménez, B. San Martín

whenever r is odd. For the matrices M(α, h) in (17) and S(ℓ, k, r) we obtain

S(ℓ, k, r) = M (\sqrt{d}, 2 cos \frac{ℓπ}{r + 1}) , ℓ = 1, …, ⌊r/2⌋

and by the results from Section 4, their energies are bounded as follows, for ℓ = 1, …, ⌊r/2⌋,

−2\sqrt{d} cos \frac{π}{k} < E(S(ℓ, k, r)) − 2\sqrt{d} (b + cos \frac{π}{k + 1}) < B(ℓ, k, r)

for ℓ = 1, …, ⌊r/2⌋, and even k, and

−2\sqrt{d} cos \frac{π}{k} < E(S(ℓ, k, r))−2\sqrt{d} (b + cos \frac{π}{k + 1}) < B(ℓ, k, r)−2\sqrt{d} cos \frac{⌊k/2⌋π}{k}

for ℓ = 1, …, ⌊r/2⌋, and odd k, By Theorem 4 we have

B(ℓ, k, r) = min{B_{1}(ℓ, k, r) , B_{2}(ℓ, k, r)} , ℓ = 1, …, ⌊r/2⌋ where

B_{1}(ℓ, k, r) = max \{2\sqrt{d} cos \frac{π}{2k + 1} , 4 cos \frac{ℓπ}{r + 1} cos \frac{π}{2k + 1}\} , ℓ = 1, …, ⌊r/2⌋

and

B_{2}(ℓ, k, r) = max \{2\sqrt{d} , \sqrt{d} + 2 cos \frac{ℓπ}{r + 1}\} , ℓ = 1, …, ⌊r/2⌋ .

From this we obtain

2 ∑_{ℓ=1}^{⌊r/2⌋} E(S(ℓ, k, r)) < 4 \sqrt{d} ⌊\frac{r}{2}⌋ (b + cos \frac{π}{k + 1}) + 2 ∑_{ℓ=1}^{⌊r/2⌋} B(ℓ, k, r) (39)

and

4 ⌊\frac{r}{2}⌋ \sqrt{d} (b + cos \frac{π}{k + 1} − cos \frac{π}{k} ) < 2 ∑_{ℓ=1}^{⌊r/2⌋} E(S(ℓ, k, r))  (40)

for even k, and

2 ∑_{ℓ=1}^{⌊r/2⌋} E(S(ℓ, k, r)) < 4 \sqrt{d} ⌊\frac{r}{2}⌋ (b + cos \frac{π}{k + 1} − cos \frac{⌊k/2⌋π}{k} )+2 ∑_{ℓ=1}^{⌊r/2⌋} B(ℓ, k, r)

Spectra of copies of Bethe trees 79

and

4 ⌊\frac{r}{2}⌋ \sqrt{d} (cos \frac{π}{k + 1} + b − cos \frac{π}{k} ) < 2 ∑_{ℓ=1}^{⌊r/2⌋} E(S(ℓ, k, r)) .  (42)

for odd k.

Then for the energy E(T (d, k, r)) , from (37), (39), and (40) we obtain

E(T (d, k, r))−rE(B_{d,k})+rE(S_{k}) < 4\sqrt{d} ⌊\frac{r}{2}⌋ (cos \frac{π}{k + 1} + b)+2 ∑_{ℓ=1}^{⌊r/2⌋} B(ℓ, k, r)

and

4\sqrt{d} ⌊\frac{r}{2}⌋ (cos \frac{π}{k + 1} + b − cos \frac{π}{k} ) < E(T (d, k, r)) − rE(B_{d,k}) + rE(S_{k})

whenever k and r are even numbers. Moreover from (37), (41), and (42) we obtain

E(T (d, k, r)) − rE(B_{d,k}) + rE(S_{k})
< 4\sqrt{d} ⌊\frac{r}{2}⌋ (cos \frac{π}{k + 1} + b − cos \frac{⌊k/2⌋π}{k} ) + 2 ∑_{ℓ=1}^{⌊r/2⌋} B(ℓ, k, r)

and

4\sqrt{d} ⌊\frac{r}{2}⌋ (cos \frac{π}{k + 1} + b − cos \frac{π}{k} ) < E(T (d, k, r)) − rE(B_{d,k}) + rE(S_{k})

whenever r is an even number and k is an odd number.

From (38), (39), and (40) we obtain,

E(T (d, k, r))−rE(B_{d,k})+(r−1)E(S_{k}) < 4\sqrt{d} ⌊\frac{r}{2}⌋ (cos \frac{π}{k + 1} + b)+2 ∑_{ℓ=1}^{⌊r/2⌋} B(ℓ, k, r)

and

4\sqrt{d} ⌊\frac{r}{2}⌋ (cos \frac{π}{k + 1} + b − cos \frac{π}{k} ) < E(T (d, k, r))−rE(B_{d,k})+(r −1)E(S_{k})

whenever r is odd and k is even.

From (38), (41), and (42) we obtain,

E(T (d, k, r)) − rE(B_{d,k}) + (r − 1)E(S_{k})

< 4 \sqrt{d} ⌊\frac{r}{2}⌋ (cos \frac{π}{k + 1} + b − cos \frac{⌊k/2⌋π}{k} ) + 2 ∑_{ℓ=1}^{⌊r/2⌋} B(ℓ, k, r)

and

4 ⌊\frac{r}{2}⌋ \sqrt{d} (cos \frac{π}{k + 1} + b − cos \frac{π}{k} ) < E(T (d, k, r))−rE(B_{d,k})+(r −1)E(S_{k})

whenever r is odd and k is odd.

Example.

d k r E(T (d, k, r)) lower bound upper bound
2 5 4  105.00  97.59  114.74
2 4 3  29.78  24.90  34.21
4 4 2  130.25  124.18  137.36
4 5 3  861.58  856.63  868.31

Acknowledgment. M. R. acknowledges the support by Grant Conicyt TT-24070112, Chile. She also thanks the Centro de Modelamiento Matemático, C. M. M. Universidad de Chile for their hospitality and support. R. J. was partially supported through Grant MECESUP ANT 0001. This work was also partially supported by the Serbian Ministry of Science and Environmental Protection through Grant no. 144015G.

REFERENCES

[1] D. C v e t k o v i ć, M. D o o b, H. S a c h s, Spectra of Graphs – Theory and Application, Barth, Heidelberg, 1995.

[2] C. D. G o d s i l, I. G u t m a n, On the theory of matching polynomial, J. Graph Theory 5 (1981), 137–144.

[3] C. D. G o d s i l, B. D. M c K a y, A new graph product and its spectrum, Bull. Austral. Math. Soc. 18 (1978), 21–28.

[4] I. G u t m a n, Characteristic and matching polynomials of some compound graphs, Publ. Inst. Math. (Beograd) 27 (1980), 61–66.

[5] I. G u t m a n, The energy of a graph: Old and new results, in: A. Betten, A. Kohnert, R. Laue, A. Wassermann (Eds.), Algebraic Combinatorics and Applications, Springer–Verlag, Berlin, 2001, pp. 196–211.

[6] I. G u t m a n, Topology and stability of conjugated hydrocarbons. The dependence of total π-electron energy on molecular topology, J. Serb. Chem. Soc. 70 (2005), 441–456.

[7] O. J. H e i l m a n n, E. H. L i e b, Theory of monomer-dimer systems, Commun. Math. Phys. 25 (1972), 190–232.

[8] Y. I k e b e, T. I n a g a k i, S. M i y a m o t o, The monotonicity theorem, Cauchy’s interlace theorem and the Courant–Fischer theorem, Am. Math. Monthly, 94 (1987), 352–354.

[9] P. L a n c a s t e r, M. T i s m e n e t s k y, The Theory of Matrices, Second Edition with Applications, Academic Press, New York, 1985.

[10] V. N i k i f o r o v, The energy of graphs and matrices, J. Math. Anal. Appl. 326 (2007), 1472–1475.

[11] M. R o b b i a n o, R. J i m é n e z, L. M e d i n a, The energy and an approximation to Estrada index of some trees, MATCH Commun. Math. Comput. Chem. 61 (2009), 369–382.

[12] O. R o j o, The spectra of some trees and bounds for the largest eigenvalue of any tree, Linear Algebra Appl. 414 (2006), 199–217.

[13] O. R o j o, The spectra of a graph obtained from copies of a generalized Bethe tree, Lin. Algebra Appl. 420 (2007), 490–507.

[14] O. R o j o, L. M e d i n a, Tight bounds on the algebraic connectivity of Bethe trees, Lin. Algebra Appl. 418 (2006), 840–853.

[15] O. R o j o, M. R o b b i a n o, On the spectra of some weighted rooted trees and applications, Lin. Algebra Appl. 420 (2007), 310–328.

[16] O. R o j o, M. R o b b i a n o, An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree, Lin. Algebra Appl. 427 (2007), 138–150.

Universidad Católica del Norte Universidad de Antofagasta Antofagasta Chile

e-mail: mariarobbiano@gmail.com,
rjimenez@uantof.cl, sanmarti@ucn.cl

Faculty of Science

University of Kragujevac P. O. Box 60 34000 Kragujevac Serbia

                                                e-mail: gutman@kg.ac.yu