Sasmita Barik, Sonu Rani

School of Basic Sciences, IIT Bhubaneswar, Bhubaneswar, 752050, India

sasmita@iitbbs.ac.in, sr18@iitbbs.ac.in

Let G be a simple connected graph with vertex set {1, 2, . . . , n} and dⁱ denote the degree of vertex i in G. The ABC matrix of G, recently introduced by Estrada, is the square matrix whose ijth entry is q^di+dj−² did^j ; if i and j are adjacent, and zero; otherwise. The entries in ABC matrix represent the probability of visiting a nearest neighbor edge from one side or the other of a given edge in a graph. In this article, we provide bounds on ABC spectral radius of G in terms of the number of vertices in G. The trees with maximum and minimum ABC spectral radius are characterized. Also, in the class of trees on n vertices, we obtain the trees having first four values of ABC spectral radius and subsequently derive a better upper bound.

Keywords: tree, ABC matrix, ABC spectral radius, nonnegative matrix Mathematics Subject Classification : 05C05, 05C35, 05C50, 92E10

DOI: 10.5614/ejgta.2020.8.2.18

1. Introduction

We consider simple, finite and connected graphs only. Let G = (V (G), E(G)) be a graph on vertex set V (G) = {1, 2, . . . , n}. For i = 1, 2, . . . , n, let dⁱ be the degree of vertex i in G. The adjacency matrix of G, A(G), is a real symmetric matrix of order n whose ijth entry is 1, if i and j are adjacent(i ∼ j); and 0 otherwise. The spectrum of G, σ(G) = {λ1(G), λ2(G), . . . , λn(G)}, where λ1(G) ≥ λ2(G) ≥ · · · ≥ λn(G) is the multiset of eigenvalues of A(G). The largest eigenvalue, λ1(G), is called the spectral radius of G and is studied extensively by many researchers (see for example in [4]). Recently, in [6], Estrada provided a probabilistic interpretation of the term di+dj−2 did^j and showed that it represents the probability of visiting a nearest neighbor edge from one

Received: 24 February 2019, Revised: 14 September 2020, Accepted: 6 October 2020.

side or the other of a given edge in a graph. In context of molecular graphs, this interpretation can be related to the polarizing capacity of the bond considered. He introduced a matrix representation of these probabilities in the form of generalized ABC matrix which is a square matrix of order n, defined as Ωα(G) = (w α ij )n×n, where

\[w_{ij}^{\alpha} = \begin{cases} \left(\frac{d_i + d_j - 2}{d_i d_j}\right)^{\alpha}, & \text{if } i \sim j; \\ 0, & \text{otherwise}. \end{cases}\]

Following Chen [2], when α = 1/2, we will hereafter call it the ABC matrix and denote it by Ω(G). The eigenvalues of Ω(G) are called as the ABC eigenvalues of G. Note that Ω(G) is a real symmetric matrix with real eigenvalues. Let ϑ1(G) ≥ ϑ2(G) ≥ · · · ≥ ϑn(G) are the ABC eigenvalues of G in nonincreasing order. The largest ABC eigenvalue, ϑ1(G), is known as ABC spectral radius.

The ABC matrix of G can be viewed as a certain type of weighted adjacency matrix of G and can be expressed as [6]

\[\Omega(G) = (AD^{-1} + D^{-1}A - 2D^{-1}AD^{-1})^{\circ \frac{1}{2}},\]

where A is the adjacency matrix of G, D is the degree diagonal matrix of G, and ◦ is the entrywise operation (also known as Hadamard or Schur-operation). Note that the matrices AD⁻¹ and D⁻¹A are the transition probability matrices for random walkers on graph [18].

The atom-bond connectivity index (in short ABC index) [7] of G is defined as

\[ABC(G) = \sum_{[i,j] \in E(G)} \sqrt{\frac{d_i + d_j - 2}{d_i d_j}}.\]

It is worthy to point out that the ABC index is directly related to the ABC matrix, namely, sum of all entries of Ω(G) is equal to 2ABC(G). Also, when G is regular, the ABC matrix is a constant multiple of the adjacency matrix, namely, Ω(G) = √ 2(r−1) ^r A(G), where r is the regularity of graph G .

The ABC index is a valuable predictive index in the study of the heat of formation in alkanes [7]. Gutman et al. [14] proved that the ABC index reproduces the heat of formation with an accuracy comparable to that of high-level ab initio and DF T(MP2, B3LY P) quantum chemical calculations. For more work on ABC index, one can see [3, 5, 8, 9, 10, 11, 12, 13, 17, 19, 20]. Here, we consider the problem of studying the eigenvalues of Ω(G). Apart from the various applications of ABC matrix, our motivation came from some results on the ABC eigenvalues of G discussed in [2]. Chen [2] has supplied a bound on ABC spectral radius, namely, for a graph of order n ≥ 3 with no isolated vertices, ϑ1(G) ≥ q 2 n (n − 2R⁻1(G)), where R⁻1(G) = P [i,j] 1 did^j is the general Randic index of graph ´ G. Estrada [6] proved that for any graph G on n vetrices,

\[\frac{2}{n}\sum_{i=1}^{n}\Omega(i) \le \vartheta_1(G) \le \max_{i}\Omega(i),\]

where Ω(i) is the ith row sum of Ω(G).

In [2], the author posed the problem: For a given class of graphs, characterize the graphs with minimum or maximum ABC spectral radius ϑ1(G). In this article, we consider the class of trees on n vertices and characterize the trees with the maximum and minimum ABC spectral radius. We are able to provide the lower and upper bounds on ϑ1(G) in terms of number of vertices in G. By successively removing a tree at each step from our consideration, we are able to obtain the trees with first four largest values of the ABC spectral radius, in the class of trees on n vertices. Subsequently, we are able to provide a better upper bound on the ABC spectral radius of trees.

2. Main results

Let A and B be two square matrices of same size. We say, A dominates B, write it as A ≥ B or B ≤ A if A − B is a nonnegative matrix. If G is a connected graph then Ω(G) is an irreducible matrix. If A and B are two nonnegative irreducible matrices such that A ≥ B, then by a well known result of Perron Frobenius, it follows that λ1(A) ≥ λ1(B). For a reference, see [16]. Next is a well known result concerning the characteristic polynomial of a matrix, which we shall use frequently without any mention.

Theorem 2.1. [16] Let P be a square matrix of order n. Then the characteristic polynomial of P is

\[x^{n} - E_{1}x^{n-1} + E_{2}x^{n-2} + \dots + (-1)^{n}E_{n},\]

where E^k denotes the sum of principal minors of P of size k for 1 ≤ k ≤ n.

Note that the entries in Ω(G) are of the form qx+y−² xy , where x, y ∈ {1, 2, . . . , n}. The following result will be helpful which describes some properties of the function f(x, y) = ^x+y−² xy .

Lemma 2.1. Let n ≥ 3 and f(x, y) = ^x+y−² xy , where x, y ∈ {1, 2, . . . , n} and (x, y) 6= (1, 1). Then

\[\frac{1}{n} \le f(x, y) \le 1 - \frac{1}{n}\]

and equality holds in the upper bound if and only if (x, y) = (1, n) or (n, 1).

Proof. Since (x, y) 6= (1, 1), at least one of x, y, say x, is greater than one. Then

\[f(x,y) = \frac{1}{x} + \frac{1}{y} - \frac{2}{xy} = \frac{1}{x} + \frac{1}{y}\left(1 - \frac{2}{x}\right) \ge \frac{1}{x} \ge \frac{1}{n}.\]

Also, if x = 1, then

\[f(x,y) = 1 - \frac{1}{y} \le 1 - \frac{1}{n}\]

with equality if and only if y = n. Otherwise x ≥ 2 and

\[f(x,y) = \frac{1}{x} \left( 1 + \frac{x-2}{y} \right) \le \frac{1}{x} \left( 1 + \frac{x-2}{1} \right) = 1 - \frac{1}{x} \le 1 - \frac{1}{n}\]

with equality if and only if y = 1 and x = n. Hence the result.

The class of trees on n vertices is denoted by \(\mathcal{T}_n\). By \(P_n\), \(S_n\), and \(K_n\), we denote the path graph, star graph, and complete graph on n vertices, respectively. The trees \(S_n^2\), \(S_n^3\), \(S_n^4\), \(S_n^5\), \(S_n^6\), wherever mentioned, are meant for graphs as given in Figure 1.

Figure 1. The trees \(S_n^2\), \(S_n^3\), \(S_n^4\), \(S_n^5\), \(S_n^6\)

Let us recall the following classical result concerning bounds on the spectral radius of trees.

Lemma 2.2. Let T be a tree in \(\mathcal{T}_n\). Then \(2\cos\frac{\pi}{n+1} \leq \lambda_1(T) \leq \sqrt{n-1}\) and the equality occurs in upper bound if and only if \(T = S_n\).

Hofmeister[15] has refined the above result and obtained the following.

Lemma 2.3. [15] Let T be a tree in \(\mathcal{T}_n \setminus \{S_n, S_n^2\}\) and \(n \geq 4\). Then

\[\lambda_1(T) \le \sqrt{\frac{1}{2}(n-1+\sqrt{n^2-10n+33})}\]

and the equality holds if and only if \(T = S_n^4\).

Lemma 2.4. [1] Let T be a tree in \(\mathcal{T}_n \setminus \{S_n, S_n^2, S_n^3, S_n^4, S_n^5\}\) and \(n \geq 11\). Then \(\lambda_1(T) \leq \sqrt{\frac{1}{2}(n-1+\sqrt{n^2-14n+61})}\) and the equality holds if and only if \(T=S_n^6\).

Our results are on the ABC spectral radius of trees. Removing one tree from our consideration at each step, we have obtained bounds on the ABC spectral radius of trees on n vertices. The following result is a simple observation which provides the unique trees in \(\mathcal{T}_n\) with the maximum and minimum ABC spectral radius.

Proposition 2.1. Let T be a tree on \(n \ge 3\) vertices. Then

\[\frac{2}{\sqrt{n-1}}\cos\frac{\pi}{n+1} \le \vartheta_1(T) \le \sqrt{n-2}\]

and the equality holds in upper bound if and only if \(T = S_n\).

Proof. By Lemma 2.1, it follows that an entry in ABC matrix of T is bounded below by \(\frac{1}{\sqrt{n-1}}\) and is bounded above by \(\sqrt{\frac{n-2}{n-1}}\). Moreover the (ij)-th entry is equal to \(\sqrt{\frac{n-2}{n-1}}\) if and only if (i,j)=(1,n-1) or (n-1,1). This implies that \(\frac{1}{\sqrt{n-1}}A(T)\leq \Omega(T)\leq \sqrt{\frac{n-2}{n-1}}A(T)\) and the equality occurs in upper bound if and only if \(T=S_n\). Since both the matrices \(\Omega(T)\) and A(T) are nonnegative irreducible, we have \(\frac{1}{\sqrt{n-1}}\lambda_1(T)\leq \vartheta_1(T)\leq \sqrt{\frac{n-2}{n-1}}\lambda_1(T)\). Now using Lemma 2.2,

\[\frac{2}{\sqrt{n-1}}\cos\frac{\pi}{n+1} \le \vartheta_1(T) \le \sqrt{n-2}\]

and the equality occurs in upper bound if and only if \(T = S_n\). Hence the result.

Theorem 2.2. Let \(n \geq 9\) and \(T \in \mathcal{T}_n \setminus \{S_n\}\). Then

\[\vartheta_1(T) \le \sqrt{\frac{n^2 - 5n + 7 + \sqrt{(n-2)^2 + (n-3)^4}}{2(n-2)}}\]

and the equality holds if and only if \(T = S_n^2\).

Proof. With a suitable permutation of vertices, the ABC matrix of \(S_n^2\) can be written as

\[\Omega(S_n^2) = \begin{bmatrix} 0 & \frac{1}{\sqrt{2}} & 0 & \sqrt{\frac{n-3}{n-2}} & \cdots & \sqrt{\frac{n-3}{n-2}} \\ \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} & 0 & \cdots & 0 \\ 0 & \frac{1}{\sqrt{2}} & 0 & 0 & \cdots & 0 \\ \sqrt{\frac{n-3}{n-2}} & 0 & 0 & 0 & \cdots & 0 \\ \vdots & & & & & \\ \sqrt{\frac{n-3}{n-2}} & 0 & 0 & 0 & \cdots & 0 \end{bmatrix}.\]

Note that a nonzero principal minor in \(\Omega(S_n^2)\) is of size at most 4 and the sum of principal minors of size 2 and 4 are \(-\left(1+\frac{(n-3)^2}{n-2}\right)\) and \(\frac{(n-3)^2}{2(n-2)}\), respectively. Moreover, rest of the principal minors in \(\Omega(S_n^2)\) are zero. Thus, the ABC characteristic polynomial of \(S_n^2\) is

\[x^{n-4}\left(x^4-\left(1+\frac{(n-3)^2}{n-2}\right)x^2+\frac{(n-3)^2}{2(n-2)}\right).\]

This implies that \(\vartheta_1(S_n^2) = \sqrt{\frac{n^2 - 5n + 7 + \sqrt{(n-2)^2 + (n-3)^4}}{2(n-2)}}\). Observe that if \(T \neq S_n, S_n^2\), then maximum possible value of any entry in \(\Omega(T)\) is \(\sqrt{\frac{n-4}{n-3}}\), which implies

\[\Omega(T) \le \sqrt{\frac{n-4}{n-3}}A(T).\]

Further, since both of \(\Omega(T)\) and A(T) are nonnegative irreducible matrices, we have \(\vartheta_1(T) \leq \sqrt{\frac{n-4}{n-3}}\lambda_1(T)\), where \(T \neq S_n, S_n^2\). Then using Lemma 2.3,

\[\vartheta_1(T) \le \sqrt{\frac{n-4}{n-3}} \sqrt{\frac{n-1+\sqrt{n^2-10n+33}}{2}}.\]

Now we claim that

\[\sqrt{\frac{n-4}{n-3}}\sqrt{\frac{n-1+\sqrt{n^2-10n+33}}{2}} < \sqrt{\frac{n^2-5n+7+\sqrt{(n-2)^2+(n-3)^4}}{2(n-2)}}.\]

Squaring both sides and simplifying, we get

\[(n-4)(n-2)(n-1+\sqrt{n^2-10n+33})<(n-3)(n^2-5n+7+\sqrt{(n-2)^2+(n-3)^4}),\] that is,

\[n^{2} - 8n + 13 + (n-2)(n-4)\sqrt{n^{2} - 10n + 33} < (n-3)\sqrt{(n-2)^{2} + (n-3)^{4}}\]

For \(n \ge 9\), \(n^2 - 10n + 33 < (n-4)^2\) and \((n-3)^4 < (n-2)^2 + (n-3)^4\). Therefore it is sufficient to show that

\[n^2 - 8n + 13 + (n-2)(n-4)^2 < (n-3)^3\].

Equivalently, \(n^3 - 9n^2 + 24n - 19 < n^3 - 9n^2 + 27n - 27\), which is true. Hence, the result.

Theorem 2.3. Let \(n \geq 11\) and \(T \in \mathcal{T}_n \setminus \{S_n, S_n^2, S_n^3, S_n^5\}\). Then

\[\vartheta_1(T) \le \sqrt{\frac{3n^2 - 19n + 34 + \sqrt{(3n^2 - 19n + 34)^2 - 48(n-3)(n-4)^2}}{6(n-3)}}\]

and the equality holds if and only if \(T = S_n^4\).

Proof. With a suitable permutation of vertices, the ABC matrix of \(S_n^4\) can be written as \(\Omega(S_n^4) = W + W^T\) where \(W = [w_{ij}]\) is a matrix with only nonzero entries \(w_{12} = \sqrt{\frac{n-2}{3(n-3)}}, w_{15} = w_{16} = \cdots = w_{1n} = \sqrt{\frac{n-4}{n-3}}\) and \(w_{23} = w_{24} = \sqrt{\frac{2}{3}}\). Note that the sum of principal minors of size 2 and 4 in \(\Omega(S_n^4)\) are \(-\left(\frac{3n^2-19n+34}{3(n-3)}\right)\) and \(\frac{4(n-4)^2}{3(n-3)}\), respectively and rest of the principal minors are zero. Thus the ABC characteristic polynomial of \(S_n^4\) is

\[x^{n-4}\left(x^4-\left(\frac{3n^2-19n+34}{3(n-3)}\right)x^2+\frac{4(n-4)^2}{3(n-3)}\right).\]

This implies that \(\vartheta_1(S_n^4) = \sqrt{\frac{3n^2 - 19n + 34 + \sqrt{(3n^2 - 19n + 34)^2 - 48(n - 3)(n - 4)^2}}{6(n - 3)}}\).

Observe that if \(T \neq S_n, S_n^2, S_n^3, S_n^4, S_n^5\), then maximum possible value of any entry in \(\Omega(T)\) is \(\sqrt{\frac{n-5}{n-4}}\) which means \(\Omega(T) \leq \sqrt{\frac{n-5}{n-4}}A(T)\). Further since both of \(\Omega(T)\) and A(T) are nonnegative irreducible matrices, we obtain \(\vartheta_1(T) \leq \sqrt{\frac{n-5}{n-4}}\lambda_1(T)\). Using Lemma 2.4,

\[\vartheta_1(T) \le \sqrt{\frac{n-5}{n-4}} \sqrt{\frac{1}{2}(n-1+\sqrt{n^2-14n+61})}.\]

Next, we claim that

\[\sqrt{\frac{n-5}{n-4}}\sqrt{\frac{(n-1+\sqrt{n^2-14n+61})}{2}} < \vartheta_1(S_n^4).\]

Squaring both sides, we get

\(\frac{n-5}{2(n-4)}(n-1+\sqrt{n^2-14n+61})<\frac{3n^2-19n+34+\sqrt{(3n^2-19n+34)^2-48(n-3)(n-4)^2}}{6(n-3)}.\) That is, we need to show that f(n)< g(n), where

\[f(n)=3(n-3)(n-5)(n-1+\sqrt{n^2-14n+61})\] and \(g(n)=(n-4)(3n^2-19n+34+\sqrt{(3n^2-19n+34)^2-48(n-3)(n-4)^2}).\) For \(n=11,12,13,14,15\), the inequality can be verified manually. Suppose \(n\geq 16\). Then \(n^2-14n+61<(n-\frac{19}{3})^2\) which implies that

\[f(n) < 3(n-3)(n-5)\left(n-1+n-\frac{19}{3}\right) = 6n^3 - 70n^2 + 266n - 330.\] (1)

Also, \[(3n^2 - 19n + 34)^2 - 48(n - 3)(n - 4)^2\]
= \(\left(3n^2 - 27n + \frac{182}{3}\right)^2 + 64n - \frac{1984}{9} > \left(3n^2 - 27n + \frac{182}{3}\right)^2\).

Therefore,

\[g(n) = (n-4)\left(3n^2 - 19n + 34 + \sqrt{(3n^2 - 19n + 34)^2 - 48(n-3)(n-4)^2}\right)\] \[> (n-4)\left(3n^2 - 19n + 34 + 3n^2 - 27n + \frac{182}{3}\right)\] \[= (n-4)\left(6n^2 - 46n + \frac{284}{3}\right) = 6n^3 - 70n^2 + \frac{836}{3}n - \frac{1136}{3}.\]

That is,

\[g(n) > 6n^3 - 70n^2 + \frac{836}{3}n - \frac{1136}{3}. (2)\]

From equation (1) and (2), we obtain \(f(n) - g(n) < -\frac{38}{3}n + \frac{146}{3} < 0\). Hence, our claim is justified.

The following two lemmas are needed to obtain the third and fourth tree in \(\mathcal{T}_n\).

Lemma 2.5. Let \(n \geq 10\), then

\[\vartheta_1(S_n^3) = \sqrt{\frac{2n^2 - 13n + 23 + \sqrt{(2n^2 - 13n + 23)^2 - 4(n-3)(4n^2 - 31n + 61)}}{4(n-3)}},\]

and \(\vartheta_1(S_n^3) > \vartheta_1(S_n^4)\).

Proof. With a suitable permutation of vertices, the ABC matrix of \(S_n^3\) can be written as

\[\Omega(S_n^3) = \begin{bmatrix} 0 & \frac{1}{\sqrt{2}} & 0 & 0 & \sqrt{\frac{n-4}{n-3}} & \cdots & \sqrt{\frac{n-4}{n-3}} \\ \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} & 0 & 0 & \cdots & 0 \\ 0 & \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} & 0 & \cdots & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & 0 & 0 & \cdots & 0 \\ \sqrt{\frac{n-4}{n-3}} & 0 & 0 & 0 & 0 & \cdots & 0 \\ \vdots & & & & & & \\ \sqrt{\frac{n-4}{n-3}} & 0 & 0 & 0 & 0 & \cdots & 0 \end{bmatrix}.\]

Note that the sum of principal minors of size 2 and 4 in \(\Omega(S_n^3)\) is \(-\frac{(n-4)^2}{n-3}-\frac{3}{2}=\frac{2n^2-13n+23}{-2(n-3)}\) and \(\frac{(n-4)^2}{n-3}+\frac{1}{4}=\frac{4n^2-31n+61}{4(n-3)}\), respectively, and rest of the principal minors are zero. Therefore, the ABC characteristic polynomial of \(S_n^3\) is

\[x^{n-4}\left(x^4-\left(\frac{2n^2-13n+23}{2(n-3)}\right)x^2+\frac{4n^2-31n+61}{4(n-3)}\right).\]

This implies that \(\vartheta_1(S_n^3) = \sqrt{\frac{2n^2-13n+23+\sqrt{(2n^2-13n+23)^2-4(n-3)(4n^2-31n+61)}}{4(n-3)}}.\)

We claim that \(\vartheta_1(S_n^3) > \vartheta_1(S_n^4)\), where the expression for \(\vartheta_1(S_n^4)\) is given in Theorem 2.3. Squaring both sides and then cross-multiplying, we get

\[3\left(2n^2 - 13n + 23 + \sqrt{(2n^2 - 13n + 23)^2 - 4(n - 3)(4n^2 - 31n + 61)}\right)\]
> \(2\left(3n^2 - 19n + 34 + \sqrt{(3n^2 - 19n + 34)^2 - 48(n - 3)(n - 4)^2}\right)\),

which means

\[3\sqrt{(2n^2 - 13n + 23)^2 - 4(n - 3)(4n^2 - 31n + 61)}\]
> \(n - 1 + 2\sqrt{(3n^2 - 19n + 34)^2 - 48(n - 3)(n - 4)^2}\).

It can be seen that

\[(3n^2 - 19n + 34)^2 - 48(n - 3)(n - 4)^2\]
= \((3n^2 - 27n + 65)^2 - (26n^2 - 298n + 765) < (3n^2 - 27n + 65)^2\).

Therefore, it suffices to show that

\[3\sqrt{(2n^2 - 13n + 23)^2 - 4(n - 3)(4n^2 - 31n + 61)} > n - 1 + 2(3n^2 - 27n + 65).\]

Again squaring both sides and simplifying, we have \(24n^3 - 460n^2 + 2748n - 5292 > 0\), which is true for \(n \ge 10\). Hence, the result.

Lemma 2.6. Let \(n \geq 7\), then

\[\vartheta_1(S_n^5) = \sqrt{\frac{2n^2 - 15n + 31 + \sqrt{(2n^2 - 15n + 31)^2 - 8(n - 3)(n^2 - 9n + 20)}}{4(n - 3)}},\]

and \(\vartheta_1(S_n^5) < \vartheta_1(S_n^4)\).

Proof. With a suitable permutation of vertices, the ABC matrix of \(S_n^5\) can be written as

\[\Omega(S_n^5) = \begin{bmatrix} 0 & \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} & 0 & \sqrt{\frac{n-4}{n-3}} & \cdots & \sqrt{\frac{n-4}{n-3}} \\ \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} & 0 & 0 & 0 & \cdots & 0 \\ 0 & \frac{1}{\sqrt{2}} & 0 & 0 & 0 & 0 & \cdots & 0 \\ \frac{1}{\sqrt{2}} & 0 & 0 & 0 & \frac{1}{\sqrt{2}} & 0 & \cdots & 0 \\ 0 & 0 & 0 & \frac{1}{\sqrt{2}} & 0 & 0 & \cdots & 0 \\ \sqrt{\frac{n-4}{n-3}} & 0 & 0 & 0 & 0 & 0 & \cdots & 0 \\ \vdots & & & & & & \\ \sqrt{\frac{n-4}{n-3}} & 0 & 0 & 0 & 0 & 0 & \cdots & 0 \end{bmatrix}.\]

Note that the sum of principal minors of size 2,4,6 in \(\Omega(S_n^5)\) is \(-2-\frac{(n-4)(n-5)}{n-3},\frac{3}{4}+\frac{(n-4)(n-5)}{n-3}\) and \(-\frac{(n-4)(n-5)}{4(n-3)}\), respectively. The rest of principal minors are zero. Therefore, the ABC characteristic polynomial of \(S_n^5\) is

\[x^{n-6}\left(x^6 - \left(2 + \frac{(n-4)(n-5)}{n-3}\right)x^4 + \left(\frac{3}{4} + \frac{(n-4)(n-5)}{n-3}\right)x^2 - \frac{(n-4)(n-5)}{4(n-3)}\right).\]

Thus, \(\vartheta_1(S_n^5)\) is the square-root of the largest root of following polynomial

\[f(x) = x^3 - \left(2 + \frac{(n-4)(n-5)}{n-3}\right)x^2 + \left(\frac{3}{4} + \frac{(n-4)(n-5)}{n-3}\right)x - \frac{(n-4)(n-5)}{4(n-3)}\]\[= \frac{(2x-1)\left(2(n-3)x^2 - (2n^2 - 15n + 31)x + (n^2 - 9n + 20)\right)}{4(n-3)}.\]

Now, \[f(x)=0\] if and only if \(x=\frac{1}{2}\) or \(\frac{2n^2-15n+31\pm\sqrt{(2n^2-15n+31)^2-8(n-3)(n^2-9n+20)}}{4(n-3)}\). Since

\[\frac{1}{2} < \frac{2n^2 - 15n + 31 + \sqrt{(2n^2 - 15n + 31)^2 - 8(n - 3)(n^2 - 9n + 20)}}{4(n - 3)},\]

it follows that

\[\vartheta_1(S_n^5) = \sqrt{\frac{2n^2 - 15n + 31 + \sqrt{(2n^2 - 15n + 31)^2 - 8(n - 3)(n^2 - 9n + 20)}}{4(n - 3)}}.\]

Now to show that ϑ1(S 5 n ) < ϑ1(S 4 n ), it suffices to show

\[3\left(2n^2 - 15n + 31 + \sqrt{(2n^2 - 15n + 31)^2 - 8(n - 3)(n^2 - 9n + 20)}\right)\] \[< 2\left(3n^2 - 19n + 34 + \sqrt{(3n^2 - 19n + 34)^2 - 48(n - 3)(n - 4)^2}\right).\]

Equivalently, it suffices to show that

\[3\sqrt{(2n^2 - 15n + 31)^2 - 8(n - 3)(n^2 - 9n + 20)} < 7n + 5 + 2\sqrt{(3n^2 - 19n + 34)^2 - 48(n - 3)(n - 4)^2}.\] (3)

It can be easily verified that for n ≥ 7,

\[(2n^2 - 15n + 31)^2 - 8(n - 3)(n^2 - 9n + 20) < (2n^2 - 16n + 38)^2\]

and

\[(3n^2 - 19n + 34)^2 - 48(n-3)(n-4)^2 > (3n^2 - 27n + 60)^2.\]

Therefore, the left side of (3) is less than 3(2n ² − 16n + 38) and the right side of (3) is greater than 7n + 5 + 2(3n ² − 27n + 60). Further,

\[3(2n^2 - 16n + 38) < 7n + 5 + 2(3n^2 - 27n + 60)\]

is true for n ≥ 7, which proves the inequality (3). Hence, the result.

The following two theorems provide us the trees with the third and fourth largest ABC spectral radius. The results are immediate from Theorem 2.3, Lemma 2.5 and Lemma 2.6.

Theorem 2.4. Let n ≥ 11 and T ∈ Tⁿ \ {Sn, S^{2 n}}. Then

\[\vartheta_1(T) \le \sqrt{\frac{2n^2 - 13n + 23 + \sqrt{(2n^2 - 13n + 23)^2 - 4(n - 3)(4n^2 - 31n + 61)}}{4(n - 3)}},\]

and the equality holds if and only if T = S 3 n .

Theorem 2.5. Let n ≥ 11 and T ∈ Tⁿ \ {Sn, S² n , S^{3 n}}. Then

\[\vartheta_1(T) \le \sqrt{\frac{3n^2 - 19n + 34 + \sqrt{(3n^2 - 19n + 34)^2 - 48(n-3)(n-4)^2}}{6(n-3)}},\]

and the equality holds if and only if T = S 4 n .

Conclusion

We prove that for any tree on n vertices, \(2\cos\frac{\pi}{n+1} \leq \vartheta_1(T) \leq \sqrt{n-2}\). Then refining this upper bound on \(\vartheta_1(T)\) at each step, we have obtained that \(S_n, S_n^2, S_n^3, S_n^4\) are the trees with first four values of \(\vartheta_1(T)\) in \(\mathcal{T}_n\). As expected, we notice that ordering of trees according the ABC spectral radius is different than the ordering of trees according the spectral radius as given in Hofmeister [15].

It is easy to see that, when G is a regular graph of regularity r, \(\Omega(G) = \frac{\sqrt{2(r-1)}}{r}A(G)\). So, in some sense spectrum of both the matrices contain the same information about the graph. For example, the graph with largest spectral radius is n-1 regular graph \(K_n\) which is also the graph with largest \(\vartheta_1(G)\). However, in case of nonregular graphs, \(\Omega(G)\) would contain more information than A(G). It seems that ABC spectrum may lead to some new and nontrivial results on graph structure.

Acknowledgments

The second author acknowledges the financial support from CSIR, Government of India.

References

• [1] A. Chang and Q. Huang, Ordering trees by their largest eigenvalues, Linear Algebra Appl. 370 (2003), 175–184.
• [2] X. Chen, On ABC eigenvalues and ABC energy, Linear Algebra Appl. 544 (2018), 141–157.
• [3] J. Chen, J. Liu, and X. Guo, Some upper bounds for the atom-bond connectivity index of graphs, Appl. Math. Lett., 25 (2012), 1077–1081.
• [4] D. Cvetković and P. Rowlinson, The largest eigenvalue of a graph: A survey, Linear Multilinear Algebra, 544 (1990), 141–157.
• [5] K.C. Das, Atom-bond connectivity index of graphs, Discrete Appl. Math., 158 (2010), 1181–1188.
• [6] E. Estrada, The ABC matrix, J. Math. Chem., 55 (2017), 1021–1033.
• [7] E. Estrada, L. Torres, L. Rodríguez, and I. Gutman, An atom-bond connectivity index: modelling the enthalpy of formation of alkanes, Indian J. Chem., 37(A) (1998), 849–855.
• [8] G.H. Fath-Tabar, B. Vaez-Zadeh, A.R. Ashrafi, and A. Graovac, Some inequalities for the atom-bond connectivity index of graph operations, Discrete Appl. Math., 159 (2011), 1323–1330.
• [9] B. Furtula, A. Graovac, and D. Vukičević, Atom-bond connectivity index of trees, Discrete Appl. Math., 157 (2009), 2828–2835.

• [10] B. Furtula, I. Gutman, and M. Ivanovic, D. Vuki ´ cevi ˇ c, Computer search for trees with mini- ´ mal ABC index, Appl. Math. Comput., 219 (2012), 768–772.
• [11] L. Gan, H. Hou, and B. Liu, Some results on atom-bond connectivity index of graphs, MATCH Commun. Math. Comput. Chem., 66 (2011), 669–680.
• [12] I. Gutman and B. Furtula, Trees with smallest atom-bond connectivity index, MATCH Commun. Math. Comput. Chem., 68 (2012), 131–136.
• [13] I. Gutman, B. Furtula, and M. Ivanovic, Notes on trees with minimal atom-bond connectivity ´ index, MATCH Commun. Math. Comput. Chem., 67 (2012), 467–482.
• [14] I. Gutman, J. Tosovi ˇ c, S. Radenkovi ´ c, and S. Markovi ´ c, On atom-bond connectivity index ´ and its chemical applicability, Indian J. Chem., 51(A) (2012), 690–694.
• [15] M. Hofmeister, On the two largest eigenvalues of trees, Linear Algebra Appl., 260 (1997), 43–59.
• [16] R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge Uni. Press, New York, (2013).
• [17] W. Lin, X. Lin, T. Gao, and X. Wu, Proving a conjecture of Gutman concerning trees with minimal ABC index, MATCH Commun. Math. Comput. Chem., 69 (2013) 549–557.
• [18] L. Lovasz, Random walks on graphs: A Survey, ´ Combinatorics Paul Erdos is Eighty ˝ , 2 (1993) 1–46.
• [19] R. Xing, B. Zhou, and Z. Du, Further results on atom-bond connectivity index of trees, Discrete Appl. Math., 158 (2010), 1536–1545.
• [20] R. Xing, B. Zhou, and F. Dong, On atom-bond connectivity index of connected graphs, Discrete Appl. Math., 159 (2011) 1617–1630.