ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 14 (2018) 197-207
https://doi.org/10.26493/1855-3974.992.68d
(Also available at http://amc-journal.eu)
Trees with small spectral gap
Ivana Jovovic *, Tamara Koledin
Faculty of Electrical Engineering, University of Belgrade, Bulevar Kralja Aleksandra 73, 11 000 Belgrade, Serbia
Zoran Stanic f
Faculty of Mathematics, University of Belgrade, Studentski trg 16, 11 000 Belgrade, Serbia
Received 7 December 2015, accepted 20 April 2017, published online 25 August 2017
Continuing the previous research, we consider trees with given number of vertices and minimal spectral gap. Using the computer search, we conjecture that this spectral invariant is minimized for double comet trees. The conjecture is confirmed for trees with at most 20 vertices; simultaneously no counterexamples are encountered. We provide theoretical results concerning double comets and putative trees that minimize the spectral gap. We also compare the spectral gap of regular graphs and paths. Finally, a sequence of inequalities that involve the same invariant is obtained.
Keywords: Graph eigenvalues, double comet, extremal values, numerical computation. Math. Subj. Class.: 05C50, 65F15
1 Introduction
We use standard graph-theoretic terminology and notation. For example, for a graph G, n = n(G) and m = m(G) denote its order and size, while A = A(G) stands for its adjacency matrix. The characteristic polynomial of A is the characteristic polynomial of G, denoted PG. Its roots are the eigenvalues of G, denoted Ai(G) > A2(G) > • • • > An(G). Non-isomorphic graphs that share the same spectrum are said to be cospectral.
* Research is partially supported by Serbian Ministry of Education, Science and Technological Development, Project 174032.
t Research is partially supported by Serbian Ministry of Education, Science and Technological Development, Projects 174012 and 174033.
E-mail address: ivana@etf.rs (Ivana Jovovic), tamara@etf.rs (Tamara Koledin), zstanic@matf.bg.ac.rs, zstanic@math.rs (Zoran Stanic)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
Abstract
197
Ars Math. Contemp. 14 (2018) 117-128
The difference between the first two eigenvalues 5(G) = Ai(G) - A2 (G) is called the spectral gap of G. In the previous investigation (see [13]), graphs with small spectral gap are considered. The purpose of this paper is to continue this investigation in the case of trees (this part can be considered as counterpart to [13], as well), consider regular graphs with small spectral gap, and give certain upper and lower bounds for this spectral invariant.
As announced in the Abstract, we conjecture that a minimal spectral gap of trees with given order is attained for a double comet tree (the conjecture is formulated in the very beginning of the next section). We also give certain theoretical and computational results supporting this conjecture, and consider cospectrality of double comets. The conjecture is open, but nevertheless we give additional (structural and spectral) properties of a tree with minimal spectral gap.
Next, we compare the spectral gap of regular graphs and paths by showing that, under some restrictions, the spectral gap of a regular graph is bounded from below by the spectral gap of the corresponding path. Finally, we give some new bounds on 5 expressed in terms of order, size, clique number, and minimal or maximal vertex degree.
We conclude this section by certain terminology and notation. The main results are given in Sections 2-4.
We use Pn, Cn, Kn, and Kni,„2 (n1 + n2 = n) to denote the path, cycle, complete graph (or clique), and complete bipartite graph on n vertices, respectively. The disjoint union of graphs G and H is denoted by G U H, while the disjoint union of k copies of G is denoted by kG.
The generalized double comet C*(k1; k2, l), where k1,k2 > 0 and l > 2, is a tree obtained by attaching k1 pendant vertices at one end of the path P; and k2 pendant vertices at the other end of the same path. The path P; is referred to as the internal path. The double comet C(k, l) is obtained from C* (k1,k2,l) for k1 = k2 = k.
2 Spectral gap of trees
We start with the following conjecture.
Conjecture 2.1. Among all trees of order n, the spectral gap is minimized for some double comet.
The conjecture is confirmed by computer search for trees with at most 20 vertices. In all situations, there is a unique tree attaining the minimal spectral gap. For n < 8, this is the path Pn (which is a special case of double comet), for 9 < n < 11 this is C(2, n - 4), for 12 < n < 15 this is C(3, n - 6), and for 16 < n < 20 this is C(4, n - 8).
If A and A' (< A) are the largest and second largest degree in a tree T and the distance between the vertices having these degrees is at least three, then using the Interlacing Theorem (cf. [14, Theorem 1.6]), we get A2(T) > A1(K1,a' ) = %/A7. In other words, a/A7 makes a lower bound on A2(T). Since an increase in A' increases this bound, it is natural to assume that the spectral gap is minimized for a tree with two vertices of maximal degree. We provide more theoretical results supporting Conjecture 2.1.
Theorem 2.2. In the set of trees of order n (n > 2) and two vertices of maximal degree A, the largest eigenvalue A1 is minimized for the double comet C (A - 1, n - 2(A - 1)).
Proof. Clearly, the statement holds for A < 2. Assume next that u, v are the two vertices of degree A (> 3) in a tree T and let N(u), N(v) be their open neighbourhoods. Then,
I. Jovovic, T. Koledin and Z. Stanic: Trees with small spectral gap
199
removing a pendant vertex which does not belong to N(u) U N(v) (if such a vertex does not exist, then T is the required double comet) impose a strict decrease in Ai (as a consequence of the Perron-Frobenius Theorem, cf. [2, Theorem 1.3.6]). In addition, by the well-known result of Hoffman and Smith [4], inserting a vertex in the unique path between u and v is again followed by a strict decrease in Ai . Therefore, rearranging a described pendant vertex into the corresponding path gives a tree with smaller largest eigenvalue. Repeating this procedure, after finite number of steps, we arrive at C(A - 1, n - 2(A - 1)). □
In the following theorem we use another result of Hoffman [3]: Let H be the graph obtained from a graph G by attaching a hanging path of an arbitrary length at any vertex v (of G) of the degree at least two. When the length of the path attached tends to infinity then the largest eigenvalue of H increases and tends to the largest root of the equation
f (x) = ^X + ^ - PG(x) - PG-V (x) = 0,
whenever the largest eigenvalue of H is greater than 2.
Now we have the following theorem comparing spectral gaps of generalized double comets with equal internal paths.
Theorem 2.3. Given a generalized double comet C *(k1, k2, l). If I > 2 and k1 < k2 - 2, then ¿(C*(ki, k2, l)) > ¿(C*(ki + 1, ^ - 1, /)).
Proof. Let, for short, T (resp. S) stand for C*(k1, k2, l) (resp. C*(k1 + 1, k2 - 1, l)).
We have A1(T) > A1(S), as proved in [12], and so it remains to prove that A2(T) < A2 (S). First, we consider the three singular cases.
For l = 2, Using the Schwenk formula [2, Theorem 2.4.3], we compute
where
PT (x) = xfcl+fc2-2Q(x) and PS (x) = xfcl+fc2-2R(x),
Q(x) = (x4 - (k1 + k2 + 1)x2 +	and
R(x) = (x4 - (k1 + k2 + 1)x2 + k1k2 - k1 + k2 - ^ .
The second largest eigenvalues of both trees coincide with second largest roots of the polynomials Q and R. Since R(x) - Q(x) = -k1 + k2 - 1 > 0, we get A2(T) < A2(S).
For l = 3, by removing the vertex of maximal degree in T and using the interlacing argument, we get A2(T) < k1 + 1. Similarly, by removing the middle vertex of the internal path in S, we get A2 (S) > yjk1 + 1, and we are done.
For l = 4, following the case l = 2, we get that the characteristic polynomials of trees T and S are PT(x) = xfcl+fc2-2Q1(x) and PS(x) = xkl+k2-2R1(x), where the polynomials Q1 and R1 are computed in a similar way, while their difference is R1(x) - Q1(x) = (k1 - k2 + 1)(1 - x2). Computing this value for x = A2(T), we get the assertion.
Let now l > 5. For k1 =2 we directly get A2(T) < 2 < A2(S), and similarly for k1 = 1. Let in further T' stand for the non-trivial component of the graph obtained by removing the vertex of degree k2 + 1 in T. By interlacing we have A2 (T) < A1 (T'). Since k1 > 3, we may apply the result given before Theorem 2.3 to get that A1(T') is less than the largest root of
2 (x + Vx2 - ^ PKi,k1 (x) - PkiKi (x),
200
Ars Math. Contemp. 14 (2018) 197-207
k +1 k + 2
k + l - 1 k +
Figure 1: Double comet C(k, 1).
k+l+1 k+l+2
2k + l - 1
2k + l
that is the largest root of
1 ^x + \Jx2 — 4j (x2 — k2) — x.
Setting x = \Jki + 2, the last expression becomes equal to Vki — 2, i.e. it is positive in this point, which implies Ai(T') < Vki + 2.
On the other hand, using interlacing once again, we get A2(S) > yjki + 2, which completes the proof.	□
In other words, in the set of generalized double comets with fixed internal path Pl, the minimal spectral gap is attained when the cocliques on ki and k2 vertices are as equal as possible.
In order to compute the spectral gap of an arbitrarily large double comet, we derive formulas for computing its largest and second largest eigenvalue. The following two results may be viewed as a counterpart to [13, Proposition 2.4].
Theorem 2.4. If Ai(C(k, 1)) > 2, then Ai(C(k, 1)) is equal to 2cosh(2t), where t is the unique positive root of
(e2i(l-i) + l) k — e-4t (e4i + l) (e2i(l+i) + l) = 0.
(2.1)
Proof. Let the vertices of C(k, 1) be labeled l, 2,..., 2k +1 in natural order (see Figure 1),
and let an eigenvector associated with Ai = Ai(C (k, 1)) be denoted x = (xi, x2,..., xn)T. Then we have
Aixi = Exj (l < i < 2k + 1).	(2.2)

Using (2.2), we derive (2.1) in the following way. First, using the symmetry of C(k, 1), we may assume that xi = x2 = • • • = xfc = xfc+i+i = xfc+i+2 = • • • = x2fc+i (cf. [3]). Since the coordinates of the eigenvector x are of the same sign and the eigenvector itself is determined up to a multiplicative constant, we may take xi = Ai. Then, we have
xk+i = xh+l = Ai.
(2.3)
For 0 < i < 1 — l, using (2.2), we arrive at the following system of recurrence equations
xfc+j — Aixfc+i+i + xfc+i+2 =0 (l < i < 1 — l).	(2.4)
1
2
k1
k
I. Jovovic, T. Koledin and Z. Stanic: Trees with small spectral gap
201
The former equality, that is (2.3), may be regarded as a boundary condition for (2.4).
ving the re which yields
Solving the related characteristic equation t2 - Ait + 1 = 0, we get ti = -i = Al+A>2Al 4
xfc+i+i = citk+i+1 + C2t-(k+i+1).	(2.5)
Setting i = k + 2 and i = k + l - 1 in (2.2), we deduce that
Xfc+2 = Xk+i—i = Ai(A2 - k).
Next, using the first, and then the second equality in the last chain, we get c2 = cit2k+l+i and ci = fc'+12(Alfc—1, respectively. Substituting these expressions in (2.5) and using our boundary condition, we get
Ai (tj+2 + tk+l—i) = (A2 - k) (tj+i + tk+') .
Finally, using the obtained expression for ti and setting A2 = 2cosh(2t), after a straightforward computation we arrive at (2.1).
A simple analysis shows that the equation (2.1) has a positive real root. Moreover, it must be unique, because otherwise we would have two non-collinear eigenvectors corresponding to a simple eigenvalue A2. This observation completes the proof.	□
Our next result is obtained in the same way. We omit the proof and refer the reader to the previous theorem and [13].
Theorem 2.5. If A2(C(k, l)) > 2, then A2(C(k, l)) is equal to 2cosh(2t), where t is the unique positive root of
(> - e2i('+i^ (k - 1) + e2-(I+3) - 1 = 0.	(2.6)
The last two theorems enable us to compute the spectral gap of an arbitrary double comet. All what we need is to find the positive roots of (2.1) and (2.6) by means of numerical computation. In this way we get the trees with extremely small spectral gaps. For example, we have the following results for double comets determined by parameters (k, l):
(k, l)	(10,10)	(50,10)	(100,10)	(4,10) (4, 50)	(4,100)
5 «	0.0001	1.7 • 10—7	1.0 • 10—8	0.0073 2.1 • 10—i2	2.5 • 10—24
So, Conjecture 2.1 remains open. If, for some n there exists a tree which is not a double comet but has the minimal spectral gap then, by the previous computation, its spectral gap is very close to zero. Moreover, its second largest eigenvalue must be simple, as proved in our next statement.
Theorem 2.6. If T is a graph with minimal spectral gap in the set of trees of order n, then A2(T) > A3(T).
Proof. Assume to the contrary. Since T is a tree, it contains a vertex with two hanging paths attached. If these paths are Pni and Pn2 where, say ni > n2 > 2, then let T' be the tree obtained by the relocation of the endvertex of Pn2 to the end of Pni. It is known from numerous literature, see for example [14, Lemma 1.29(i)], that A2(T) > A2(T'). Next, since A2(T) = A3(T), by interlacing, we get A2(T) < A2(T'). Altogether, £(T) > J(T'), a contradiction.	□
202	Ars Math. Contemp. 14 (2018) 117-128
Recall that, according to the computer search, for n < 20, there is a unique tree that minimizes the spectral gap. So, there is another question: is such a tree unique for all n? A contribution to this question may be given by considering cospectrality of double comet graphs. It is not difficult to see that no every double comet has the unique spectrum (an easy exercise for the reader: show that C(2, l) is cospectral with C4 U P;). However, connected graphs that are cospectral with double comets are more interesting in our context. Here we provide the following result.
Theorem 2.7. The double comet C(k, 2) is cospectral with a connected graph if and only if k = t2 — t + I, for t € N. The spectrum of a double comet C (k, l), 3 < l < 5, is unique in the set of connected graphs.
Sketch proof. Observe that cospectral graphs have equal orders and sizes, and therefore if a connected graph is cospectral with a double comet, then such a graph must be a tree. Next, recall from [6] that the multiplicity of zero (also known as nullity) in the spectrum of a tree is n — 4 if and only if that tree is a generalized double comet C*(ki, k2, l), for 2 < l < 3. Similarly, the trees of nullity n — 6 are those illustrated in Figure 2. Clearly, double comets specified in this theorem are covered by these sets of trees, and so to consider their cospectrality we need to compare their spectra with spectra of trees with equal number of zero eigenvalues.
For l = 2, the possible candidates are the mentioned two generalized double comets with nullity equal to n — 4. Recall (from the proof of Theorem 2.3) that the characteristic polynomial of C*(k1, k2, 2) is:
Pc.(*i,fc2,2)(x) = xfcl+fc2-2 (x4 — (ki + k2 + 1)x2 + kik2) .
Also, using the same method, we compute
Pc(fci,fc2,3)(x) = xfcl+fc2-1 (x4 — (ki + k2 + 2)x2 + kik2 + ki + k2) .
By setting ki = k2 = k in the first polynomial, we get the characteristic polynomial of C(k, 2). Next, comparing the characteristic polynomials of C(k, 2) and C* (ki, k2,2), we get ki + k2 = k and kik2 = k2, which implies ki = k2, i.e. the only solution is obtained when the corresponding trees are isomorphic.
Figure 2: Trees of nullity n — 6.
Taking into account C*(ki; k2, 3), we get ki + k2 = 2k — 1 and kik2 = (k — 1)2, which means that ki and k2 are the solutions of s2 — (2k — 1)s + (k — 1)2 = 0, i.e. they
I. Jovovic, T. Koledin and Z. Stanic: Trees with small spectral gap
203
are of the form 2fc-1±2/4fc—. Since we are interested in integral solutions, 4k - 3 must be a perfect square (clearly, an odd integer). Setting 4k - 3 = (2t - 1)2, t G N, we get k = t2 - t + 1. In addition, each k of this form gives two distinct positive values for k1 and k2, and we are done.
The cases l G {3,4, 5} are considered in exactly the same way, i.e. by comparing the corresponding characteristic polynomials and, in some situations, by reducing the procedure by using theoretic reasoning based on more sophisticated results like eigenvalue interlacing. In all cases we get that the double comet under consideration is not cospectral with any of possible candidates, and the proof follows.	□
So, in general case, a double comet may be cospectral with another graph. Even more, it may occur that this graph is connected (and then, it is also a tree). On the other hand, in our computational results double comets that are cospectral with other trees do not appear in the role of those with minimal spectral gap.
3 Comparing the spectral gap of paths and regular graphs
It is proved in [13] that the spectral gap of the path Pn is always less than the spectral gap of the cycle Cn. In other words, the spectral gap of any connected 2-regular graph is greater than ¿(P„). Perhaps surprisingly, but a similar conclusion cannot be deduced for all regular graphs. A counterexample is the regular graph illustrated in Figure 3. Its spectral gap is close to 0.105, while we simultaneously have tf(P14) « 0.129 (both values are rounded to three decimal places).
Figure 3: A regular graph whose spectral gap is smaller than the spectral gap of the corresponding path.
If the vertex degree is sufficiently large, then we have the following result.
Theorem 3.1. Let G be a connected r-regular graph of order n (n > 3). If r > 22, then
¿(G) > ¿(P„).
Proof. If n < 2r + 1, then
A2(G) = -A„(G) < Ai(G) = n - r - 2,
and so ¿(G) = Ai(G) - A2(G) > r - (n - r - 2) > 1. On the other hand, ¿(P„) < 1 holds for any n > 5, while the cases n = 3 and n = 4 are resolved easily.
204
Ars Math. Contemp. 14 (2018) 117-128
Let now n > 2r + 2. Considering S(Pn) and using the Taylor series, we get
S(P„) =
n 2n 2 cos--cos ■
n + 1
n + 1
< 2 1 - -
2 V n + 1
1
+ 77
4! I n + 1
1
1
+ TT
2n
2 ^ n
2 n + 1
2

15

= 3
< 3
2 \n + 1;
2
n
,n + 1
n + 1
1--5-
We next use the inequalities for regular graphs, S > nD [7] and D < 3[r+rJ - 1 [1], where D stands for the diameter. We compute
S(G) > nD >
3LrfrJ - 1
>
3(r+r) - 1
4(r + 1) n(3n — r — 1)
>
4(r + 1)
3n2
Since, for r > 22 it holds 3 ^n+l) < , we get the assertion.
□
4 Bounds for spectral gap
In this section we give some bounds on S(G). We start with the following lemma.
Lemma 4.1. Given a connected graph G, let K denote its proper subgraph isomorphic to either a complete graph Kp or a complete bipartite graph Kp,q. If H is a graph obtained from G by deleting all edges belonging to K, then
A2(G) < Ai(H).
Proof. Assume that G has n vertices, and K has k vertices. Since K is a proper subgraph, k < n must hold. If A is the adjacency matrix of K U (n - k)K1 and B is the adjacency matrix of H then, by applying the Courant-Weyl inequality A2(A + B) < A2(A) + A1(B) (cf. [2, Theorem 1.3.5]), we get
A2(G) < A2(K U (n - k)Ki) + Ai(H) = 0 + Ai(H).
□
In what follows, we use the following upper bound for Ak (k being a positive integer)
in terms of the clique number w and the number of k-walks wk in G [9],
Ak <
w - 1
-wk.
(4.1)
2
4
n
n
2
n
4
4
n
n
I. Jovovic, T. Koledin and Z. Stanic: Trees with small spectral gap
205
Theorem 4.2. For a connected graph G with n vertices, m edges, and the clique number w (w > 3),
S > w - 1 - jj(w - 2)	- w^J .	(4.2)
Proof. Setting k = 2 in (4.1), we get Ai < 2 ^^ m. Deleting the edges belonging to a largest clique of G and using Lemma 4.1, we get
A2(G)2 < 2w-f (m - (w
or
A2(G) < ^l(w - 2) ( ^ - w
On the other hand, Ai (G) > w - 1, and we get the assertion.	□
Analyzing the lower bound (4.2), we get w - 1 - ^J(w - 2) ^¿—i - wj > 0 whenever
11
m < —+ w(w - 1) +
2 v ' 2w - 4
In other words, this lower bound gives a non-trivial result only if the above inequality (on m) holds. Moreover, although the previous theorem is easily proved, the obtained inequality can give a good estimate in some cases. If we consider the graph G obtained from the complete graph Kp by attaching k pendant edges at one of its vertices then (4.2)
gives S < p - 1 - ^Jkp—i. Setting p =10 and k =1 we get S « 8.572. The deviation form the exact value is close to 0.390.
In the following theorem we provide more lower bounds on S. The first of them is based on the following inequality for a graph with n vertices, m edges and minimal vertex degree
dmin [5, 8]
, , dmin - 1 + \/(d min + 1)2 + 4(2m - dminn) Ai <-2-. ( )
Theorem 4.3. Let G be a connected r-regular graph with n vertices and let H be obtained form G by deleting
(a)	all edges belonging to a clique Kp (p < n),
(b)	all edges belonging to a proper induced subgraph Kp,q (p < q),
then
(a)	S(G) > r+p-V4n(p-i) + (r+2)2-3p2-2rp
(b)	S(G) > r+q+i-V4nq+2(r-q±i)!-pq if H is connected, and S(G) > r+p+W4np+(r-p+i)2-8pq-4p(r-p) if h is disconnected.
206
Ars Math. Contemp. 14 (2018) 117-128
Proof. Consider (a). By Lemma 4.1, A2(G) < Ai(H). The graph H has n vertices, rn — (2) edges, and the minimal vertex degree in H is r - p +1. Using the inequality (4.3), we get
A(g) < A(H) < r — P + v74n(P — 1) + (r + 2)2 — 3P2 — 2rP
and since A1 (G) = r, we get the assertion.
Consider now (b). If H is connected then it has n vertices, rn — Pq edges, and the minimal vertex degree in H is r — q. Using (4.3), we get the assertion. If H is disconnected then p < q = r, and it contains p isolated vertices. Excluding these vertices, we get the graph with n — p vertices and minimal vertex degree r — p. The desired inequality is again obtained by using the same argument.	□
Here is an upper bound for a special class of regular graphs.
Theorem 4.4. Let G be an r-regular graph of order n. If G is triangle free, then
¿(G) < n (2 — ^ .	(4.4)
Equality holds if G is isomorphic to Kn, n.
Proof. We have An(G) < — (n-+-1)2 (cf. [10]), and thus A2 (G) = —1 — An(G) > —1 + ("-+-1)2. Now, ¿(G) = r — A2 (G) would be less than or equal to r + 1 — (n-+-1)2 = n ^2 — r+1 j whenever this number is non-negative, i.e. whenever r > . On the other
hand, if G is triangle-free, then A 1(G) < ^m(G) (see [11]), i.e. n — r — 1 < ^"("-r-1)., which again gives r > n-2. Hence, inequality (4.4) holds for any graph specified in the theorem.
The equality is verified by direct computation.	□
References
[1]	L. Caccetta and W. F. Smyth, Graphs of maximum diameter, Discrete Math. 102 (1992), 121— 141, doi:10.1016/0012-365x(92)90047-j.
[2]	D. Cvetkovic, P. Rowlinson and S. Simic, An Introduction to the Theory of Graph Spectra, volume 75 of London Mathematical Society Student Texts, Cambridge University Press, Cambridge, 2010, doi:10.1017/cbo9780511801518.
[3]	A. J. Hoffman, On limit points of spectral radii of non-negative symmetric integral matrices, in: Y. Alavi, D. R. Lick and A. T. White (eds.), Graph Theory and Applications, Springer, Berlin, volume 303 of Lecture Notes in Mathematics, pp. 165-172, 1972, proceedings of the Conference at Western Michigan University, Kalamazoo, Michigan, May 10- 13, 1972.
[4]	A. J. Hoffman and J. H. Smith, On the spectral radii of topologically equivalent graphs, in: M. Fiedler (ed.), Recent Advances in Graph Theory, Academia, Prague, pp. 273-281, 1975, proceedings of the Second Czechoslovak Symposium held in Prague, June 1974.
[5]	Y. Hong, J.-L. Shu and K. Fang, A sharp upper bound of the spectral radius of graphs, J. Comb. Theory Ser. B 81 (2001), 177-183, doi:10.1006/jctb.2000.1997.
I. Jovovic, T. Koledin and Z. Stanic: Trees with small spectral gap
207
[6]	S. Li, On the nullity of graphs with pendent vertices, Linear Algebra Appl. 429 (2008), 1619— 1628, doi:10.1016/j.laa.2008.04.037.
[7]	B. Mohar, The Laplacian spectrum of graphs, in: Y. Alavi, G. Chartrand, O. R. Oellermann and A. J. Schwenk (eds.), Graph Theory, Combinatorics, and Applications, Volume 2, John Wiley & Sons, New York, A Wiley-Interscience Publication, pp. 871-898, 1991, proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs held at Western Michigan University, Kalamazoo, Michigan, May 30 - June 3, 1988.
[8]	V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002), 179-189, doi:10.1017/s0963548301004928.
[9]	V. Nikiforov, Walks and the spectral radius of graphs, Linear Algebra Appl. 418 (2006), 257268, doi:10.1016/j.laa.2006.02.003.
[10]	V. Nikiforov, More spectral bounds on the clique and independence numbers, J. Comb. Theory Ser. B 99 (2009), 819-826, doi:10.1016/j.jctb.2009.01.003.
[11]	E. Nosal, Eigenvalues of Graphs, Master's thesis, Univesity of Calgary, Calgary, 1970.
[12]	S. K. Simic, E. M. Li Marzi and F. Belardo, On the index of caterpillars, Discrete Math. 308 (2008), 324-330, doi:10.1016/j.disc.2006.11.046.
[13]	Z. Stanic, Graphs with small spectral gap, Electron. J. Linear Algebra 26 (2013), 417-432, doi:10.13001/1081-3810.1662.
[14] Z. Stanic, Inequalities for Graph Eigenvalues, volume 423 of London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, 2015, doi:10.1017/ cbo9781316341308.