Bulletin T.CXXII de l’Académie Serbe des Sciences et des Arts - 2001 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 26

SOME SPECTRAL PROPERTIES OF STARLIKE TREES

M. LEPOVIĆ, I. GUTMAN

(Presented at the 2nd Meeting, held on March 30, 2001)

A b s t r a c t. A tree is said to be starlike if exactly one of its vertices has degree greater than two. We show that almost all starlike trees are hyperbolic, and determine all exceptions. If k is the maximal vertex degree of a starlike tree and λ_{1} is its largest eigenvalue, then \sqrt{k} ≤ λ_{1} < k/\sqrt{k − 1} . A new way to characterize integral starlike trees is put forward.

AMS Mathematics Subject Classification (2000): 05C05, 05C50 Key Words: Starlike trees, Spectra (of graphs), Hyperbolic graphs, In-

tegral graphs

1. Introduction

A tree in which exactly one vertex has degree greater than two is said to be starlike [10]. In some recent works various spectral properties of starlike trees were studied [1, 3, 4, 6]. Among other results, it is shown that no two starlike trees are cospectral [4].

Let P_{n} denote the path on n vertices. By S(n_{1}, n_{2}, …, n_{k}) we denote the starlike tree which has a vertex v_{1} of degree k ≥ 3 and which has the property

S(n_{1}, n_{2}, …, n_{k}) − v_{1} = P_{n_{1}} ∪ P_{n_{2}} ∪ ⋯ ∪ P_{n_{k}} .  (1)

This tree has n_{1} + n_{2} + ⋯ + n_{k} + 1 vertices. Clearly, the parameters n_{1}, n_{2}, …, n_{k} determine the starlike tree up to isomorphism. In what follows, it will be assumed that n_{1} ≥ n_{2} ≥ ⋯ ≥ n_{k} ≥ 1 .

We say that the starlike tree S(n_{1}, n_{2}, …, n_{k}) has k branches, the lengths of which are n_{1}, n_{2}, …, n_{k}, respectively.

Let G be a simple graph of order n. The spectrum of G consists of the eigenvalues λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} of its (0,1)-adjacency matrix A. The characteristic polynomial of the adjacency matrix, det(λI − A) , is called the characteristic polynomial of the graph G and is denoted by ϕ(G, λ) or simply by ϕ(G) [2].

If G is a graph and v is its arbitrary vertex, then [2, 8]

ϕ(G) = λ ϕ(G − v) − ∑_{u} ϕ(G − u − v) − 2 ∑_{C} ϕ(G − C)

with the first summation on the right–hand side going over vertices u adjacent to the vertex v and the second summation over all cycles C embracing the vertex v. Applying this recurrence relation to starlike trees we obtain

ϕ(S(n_{1}, n_{2}, …, n_{k})) = λ ∏_{i=1}^{k} ϕ(P_{n_{i}}) − ∑_{i=1}^{k} [ϕ(P_{n_{i}−1}) ∏_{j∈V_{i}} ϕ(P_{n_{j}})] (2)

where V_{i} = {1, 2, …, k} \ {i}.

2. Characterization of Hyperbolic Starlike Trees

Let Γ be a Coxeter group and G the corresponding Coxeter graph. The Coxeter graph G is said to be hyperbolic if the group Γ is realizable as a reflection group in a hyperbolic space. Maxwell [5] demonstrated that G is hyperbolic if and only if it has an eigenvalue greater than 2 and all other eigenvalues are less than 2.

It happens that, with a few exceptions, all starlike trees are hyperbolic. In order to show this we need:

Lemma 1. At most one eigenvalue of a starlike tree is greater than two.

P r o o f. All the eigenvalues of the path graphs are less than two. Consequently, in view of (1), all the eigenvalues of S(n_{1}, n_{2}, …, n_{k}) − v_{1} are less than two. Therefore, by the interlacing theorem (see [2, p. 19]), S(n_{1}, n_{2}, …, n_{k}) may possess at most one eigenvalue greater than two. □

Theorem 1. All starlike trees, except S(n−3, 1, 1) for n ≥ 4 , S(5, 2, 1) , S(4, 2, 1) , S(3, 3, 1) , S(3, 2, 1) , S(2, 2, 2) , S(2, 2, 1) and S(1, 1, 1, 1) are hyperbolic.

The exceptional graphs specified in Theorem 1 are depicted in Fig. 1.

[figure: …; ^{n−3}; S(n − 3, 1, 1), n ≥ 4]

[figure: S(5, 2, 1); S(4, 2, 1)]

[figure: S(3, 3, 1); S(3, 2, 1)]

[figure: S(2, 2, 1); S(2, 2, 1); S(1, 1, 1, 1)]

Fig. 1 The only starlike trees which are not hyperbolic, i.e., which do not have the property λ_{1} > 2 > λ_{2}.

P r o o f. Theorem 1 is a proper consequence of a result by Smith [9] (see also [2, p. 78–79] which characterizes all graphs with λ_{1} ≤ 2 . What only needs to be done is to select among them those which are starlike trees. In view of Lemma 1, all other starlike trees must be hyperbolic. □

3. Bounds for the Largest Eigenvalue of a Starlike Tree

Theorem 2. If λ_{1} is the largest eigenvalue of the starlike tree S(n_{1}, n_{2}, …, n_{k}) , then \sqrt{k} ≤ λ_{1} < k/\sqrt{k − 1} holds for any positive integers n_{1} ≥ n_{2} ≥ ⋯ ≥ n_{k} ≥ 1 .

P r o o f. The lower bound is elementary because the star on k + 1 vertices is a subgraph of any starlike tree S(n_{1}, n_{2}, …, n_{k}) . The largest eigenvalue of this star is \sqrt{k}.

In order to deduce the upper bound for λ_{1} consider first the case when n_{1} = n_{2} = ⋯ = n_{k} = n and write S(k · n) instead of S(n, n, …, n) . Then Eq. (2) reduces to

ϕ(S(k · n)) = ϕ(P_{n})^{k−1} [λ ϕ(P_{n}) − (k − 1)ϕ(P_{n−1})] .

The largest eigenvalue S(k · n) is a root of the equation

λ ϕ(P_{n}) = (k − 1)ϕ(P_{n−1}) .  (3)

By substituting λ = 2 cos θ, the relation (3) becomes 2 cos θ sin(n + 1)θ/ sin θ = (k − 1) sin n θ/ sin θ. By setting t^{1/2} = e^{iθ} we arrive at

\frac{t^{n+2} − (k − 1) t^{n+1} + (k − 1) t − 1}{t − 1} = 0  (4)

that is

t^{n+1} − (k − 2) t^{n} − ⋯ − (k − 2) t + 1 = 0 .  (5)

If t_{i} and t_{i}^{−1} for i = 1, 2, …, ⌊\frac{n+1}{2}⌋ are the roots of the Eq. (5) then λ_{i}^{∗} = ± [t_{i}^{1/2} + t_{i}^{−1/2}] are the roots of Eq. (3).

Denote by Q_{n+1}(t) the polynomial in relation (5). Then for any n > 1 we have that Q_{n+1}(k − 2) < 0 and Q_{n+1}(k − 1) > 0 . Hence Q_{n+1}(t) has a zero t_{∗} in the interval (k − 2, k − 1) . Since d λ(t)/dt = d (t^{1/2} + t^{−1/2})/dt = \frac{1}{2} [1/\sqrt{t} − 1/(t\sqrt{t})] > 0 for any t > (k−2) , it follows that λ(t_{∗}) > λ(k−2) = (k−1)/\sqrt{k − 2} ≥ 2 . In view of Lemma 1 this implies that λ(t_{∗}) is the largest eigenvalue of the graph S(k · n) . Since λ_{1} = λ(t_{∗}) < λ(k − 1) = k/\sqrt{k − 1} we obtain that the statement is true for any graph S(k · n) .

The proof is now completed by setting n = n_{1} and by taking into account that λ_{1}(S(n_{1}, n_{2}, …, n_{k})) ≤ λ_{1}(S(k · n)) because S(n_{1}, n_{2}, …, n_{k}) is a subgraph of S(k · n) . □

Corollary 2.1. For any integer k > 1 ,

lim_{n→∞} λ_{1}(S(k · n)) = \frac{k}{\sqrt{k − 1}} .

P r o o f. The case when k = 2 is trivial so its proof is omitted. If k > 2 , then according to (4) it is sufficient to show that

lim_{n→∞} [t^{n+2} − (k − 1) t^{n+1} + (k − 1) t − 1] = − ∞

in the point k−1− \frac{1}{10^{m}} for any fixed positive integer m. This can be verified directly. Therefore, since Q_{n+1}(k − 1 − \frac{1}{10^{m}}) < 0 for sufficiently large values of n, we conclude that Q_{n+1}(t) has a zero in the interval (k−1− \frac{1}{10^{m}} , k−1) . □

Corollary 2.2. For any positive integer k and for n = 1 the spectrum of S(k · n) reads:

\{0 (k − 1 times) ; ± \sqrt{k}\}

for n = 2 and k ≥ 1 ,

\{± 1 (k − 1 times) ; 0 ; ± \sqrt{k + 1} \}

for n = 3 and k ≥ 1 ,

\{±\sqrt{2} (k − 1 times) ; 0 (k − 1 times) ; ± \sqrt{\frac{(k + 2) ± \sqrt{(k − 2)^{2} + 4 k}}{2}} \}

for n = 4 and k ≥ 1 ,

\{\sqrt{\frac{3 ± \sqrt{5}}{2}} (k − 1 times) ; 0 ; ± \sqrt{\frac{(k + 3) ± \sqrt{(k − 1)^{2} + 4}}{2}} \} .

4. Characterization of Integral Starlike Trees

The following result was earlier communicated by Watanabe and Schwenk [10]. The proof presented here is different and somewhat shorter. A graph is said to be integral if all its eigenvalues are integers.

Theorem 3. A starlike tree S(n_{1}, n_{2}, …, n_{k}) is integral if and only if either n_{i} = 1 for all i and \sqrt{k} is an integer, or n_{i} = 2 for all i and \sqrt{k + 1} is an integer.

P r o o f. The fact that the above specified starlike trees are integral is verified directly from Corollary 2.2. What is less easy to envisage is that there are no other integral starlike trees.

First let S(n_{1}, n_{2}, …, n_{k}) be a starlike tree with 1 ≤ n_{i} ≤ 2 for i = 1, 2, …, k, such that S(n_{1}, n_{2}, …, n_{k}) is neither S(k · 1) nor S(k · 2) . Then from Theorem 2 we obtain that k < [λ_{1}(S(n_{1}, n_{2}, …, n_{k}))]^{2} < k + 1 , implying that S(n_{1}, n_{2}, …, n_{k}) is not integral.

Consider next the case when n_{1} ≥ 4 . Since P_{n_{1}} is a subgraph of S(n_{1}, n_{2}, …, n_{k}) it follows that S(n_{1}, n_{2}, …, n_{k}) has at least one eigenvalue in the interval [2 cos \frac{3π}{n_{1}+1}, 2 cos \frac{4π}{n_{1}+1}]. Consequently, this tree cannot be integral.

What remains is to examine starlike trees for which n_{1} = 3 . Assume that there is an integral starlike tree S = S(3, n_{2}, …, n_{k}) . Using Corollary

2.2 we find that k < [λ_{1}(S)]^{2} ≤ ^{\frac{(k+2)+\sqrt{(k−2)^{2}+4 k}}{2}} < k + 2 , wherefrom it follows λ_{1}(S) = \sqrt{k + 1} (because λ_{1} is assumed to be an integer) .

It is not difficult to see that it cannot be n_{2} = 3 . Indeed, the spectrum of S(3, 3, n_{3}, …, n_{k}) contains all the eigenvalues of P_{3} among which is \sqrt{2} .

Therefore we may assume that n_{2} ≤ 2.

Further, λ_{1}(S(2, n_{2}, …, n_{k})) < λ_{1}(S) = λ_{1}(S(k · 2)) = \sqrt{k + 1} . The left–hand side inequality follows because S(2, n_{2}, …, n_{k}) is a subgraph of S(3, n_{2}, …, n_{k}) .

Because λ_{1}(S(2, n_{2}, …, n_{k})) < λ_{1}(S(k·2)) the tree S(2, n_{2}, …, n_{k}) must be a proper subgraph of S(k · 2) , and therefore n_{k} = 1 .

In order to simplify the notation we denote here S(3, n_{2}, …, n_{k}) as S(3, p· 2, q · 1) , where p and q stand for the number of branches of length two and one, respectively.

According to (2), having in mind that p = (k−1)−q, by straightforward calculation we obtain

ϕ(S(3, p · 2, q · 1)) = λ ϕ(P_{1})^{q−1} ϕ(P_{2})^{p−1} · R_{6}(λ)

where

R_{6}(λ) = λ^{6} − (k + 3) λ^{4} + (2 k + q + 2) λ^{2} − (2 q + 1) .

If p ≥ 1 then from the latter relation follows R_{6}(\sqrt{k + 1}) = 0 , wherefrom we conclude that q (k−1)−1 = 0 , i. e., q = \frac{1}{k−1} < 1 . This is a contradiction since it must be q ≥ 1 . If, however, p = 0 then the characteristic polynomial of S(3, p · 2, q · 1) reduces to

ϕ(S(3, (k − 1) · 1)) = λ ϕ(P_{1})^{k−2} · R_{4}(λ)

where

R_{4}(λ) = λ^{4} − (k + 2) λ^{2} + (2 k − 1) .

Since R_{4}(\sqrt{k + 1}) = k−2 ≥ 1 we conclude that ϕ(S(3, n_{2}, …, n_{k}) , \sqrt{k + 1}) ≠ 0 , i. e., that \sqrt{k + 1} is not an eigenvalue of S(3, n_{2}, …, n_{k}) , a contradiction. □

REFERENCES

[1] F. K. B e l l, S. K. Simić, A note on the second largest eigenvalue of star-like trees, in: G. M. Milovanović (ed.), Recent progress in inequalities, Kluwer, Dordrecht, 1998, pp. 433–443.

[2] 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.

[3] I. G u t m a n, O. A r a u j o, J. R a d a, Matchings in starlike trees, Appl. Math. Lett., in press.

[4] M. L e p o v i ć, I. G u t m a n, No starlike trees are cospectral, Discrete Math., in press.

[5] G. M a x w e l l, Hyperbolic trees, J. Algebra, 54 (1978), 46–49.

[6] J. R a d a, O. A r a u j o, Higher order connectivity index of starlike trees, Discrete Appl. Math., in press.

[7] A. J. S c h w e n k, Almost all trees are cospectral, in: F. Harary (ed.), New directions in the theory of graphs, Academic Press, New York, 1973, pp. 275–307.

[8] A. J. S c h w e n k, Computing the characteristic polynomial of a graph, in: R. A. Bari, F. Harary (eds.), Graphs and combinatorics, Springer–Verlag, Berlin, 1974, pp. 153–172.

[9] J. H. S m i t h, Some properties of the spectrum of a graph, in: R. Guy, H. Hanani, H. Sauer, J. Schönheim (eds.), Combinatorial structures and their applications, Gordon & Breach, New York, 1970, pp. 403–406.

[10] M. W a t a n a b e, A. J. S c h w e n k, Integral starlike trees, J. Austral. Math. Soc. A 28 (1979) 120–128.

Faculty of Science University of Kragujevac P.O.Box 60 YU-34000 Kragujevac Yugoslavia