Corrigendum of a Theorem on New Upper Bounds for the α-Indices. Comment on Lenes et al. New Bounds for the α-Indices of Graphs. Mathematics 2020, 8, 1668

Abstract

We give a family of counterexamples of a theorem on a new upper bound for the α-indices of graphs in the paper that is mentioned in the title. We also provide a new upper bound for corrigendum.

The Statement, Counterexamples, and Corrigendum

Let C be an $n\times n$ real symmetric matrix. The index of C, denoted by $\rho \left(C\right)$, is the largest eigenvalue of C. Let $G=(V,E)$ be a connected graph of order $n=\left|V\right|$ and size $m=\left|E\right|$ with adjacency matrix $A\left(G\right)$ and diagonal matrix $D\left(G\right)$ of degree sequence. Nikiforov [1] proposed the following matrix:

$$A_{\alpha }\left(G\right)=\alpha D\left(G\right)+(1-\alpha )A\left(G\right),$$

where $0\le \alpha \le 1$. The α-index of G, denoted by ${\rho }_{\alpha }\left(G\right)$, is the index of $A_{\alpha }\left(G\right)$. E. Lenes, E. Mallea-Zepeda, and J. Rodríguez [2] (Theorem 4) gave the following upper bound for ${\rho }_{\alpha }\left(G\right)$.

$${\rho }_{\alpha }\left(G\right)\le \frac{\delta -1+\alpha +\sqrt{{(\delta +1-\alpha )}^2+4(2m-n\delta )(1-\alpha )}}{2},$$

(1)

where $\delta$ is the minimum degree of G.

The upper bound of ${\rho }_{\alpha }\left(G\right)$ in (1) is not true by the following family of counterexamples.

 Example 1.

It was shown in [1] that the α-index of the star graph $K_{1,n-1}$ is

$${\rho }_{\alpha }\left(K_{1,n-1}\right)=\frac{1}{2}\left(\alpha n+\sqrt{{\alpha }^2{n}^2+4(n-1)(1-2\alpha )}\right).$$

Suppose $\alpha \ne 0$. Then

$$\underset{n\to \infty }{lim}\frac{{\rho }_{\alpha }\left(K_{1,n-1}\right)}{\alpha n}=1.$$

(2)

Applying $\delta =1$ for $K_{1,n-1}$ with $n\ge 2$ in (1), we find

$${\rho }_{\alpha }\left(K_{1,n-1}\right)\le \frac{1}{2}\left(\alpha +\sqrt{{(2-\alpha )}^2+4(n-2)(1-\alpha )}\right)\sim n^{\frac{1}{2}}.$$

Hence

$$\underset{n\to \infty }{lim}\frac{{\rho }_{\alpha }\left(K_{1,n-1}\right)}{\alpha n}=0,$$

a contradiction to (2).

We follow the idea of the proof of the inequality (1) in [2] and give the following corrected version.

 Theorem 1.

Let G be a connected graph of order n and size m with maximum degree Δ and minimum degree δ. Then

$${\rho }_{\alpha }\left(G\right)\le \frac{\alpha \Delta +(1-\alpha )(\delta -1)+\sqrt{{(\alpha \Delta +(1-\alpha )(\delta -1))}^2+4(1-\alpha )(2m-(n-1)\delta )}}{2}$$

for $0\le \alpha <1$. Equality holds if and only if G is regular, or $\alpha =0$ and every vertex in G has degree $n-1$ or δ.

Proof. 

Let G have the degree sequence $\Delta =d_1\ge d_2\ge \cdots \ge d_n=\delta$, and $r_i\left(C\right)$ denote the i-th row sum of an $n\times n$ matrix C. Note that $r_i\left(A_{\alpha }\left(G\right)\right)=\alpha d_i+(1-\alpha )d_i=d_i,$ and

$$\begin{array}{l}{r}_i(A_{\alpha }{\left(G\right)}^2)=\alpha d_i^2+(1-\alpha )\sum _{ij\in E}{d}_j=\alpha d_i^2+(1-\alpha )(2m-d_i-\sum _{j\ne i,ij\notin E}{d}_j)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\le \alpha \Delta d_i+(1-\alpha )(2m-d_i-(n-d_i-1)\delta )\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=(\alpha \Delta +(1-\alpha )(\delta -1))d_i+(1-\alpha )(2m-(n-1)\delta ).\end{array}$$

(3)

Therefore, for $1\le i\le n$,

$$r_i(A_{\alpha }{\left(G\right)}^2-(\alpha \Delta +(1-\alpha )(\delta -1))A_{\alpha }\left(G\right))\le (1-\alpha )(2m-(n-1)\delta ).$$

(4)

Note that $A_{\alpha }^2\left(G\right)-(\alpha \Delta +(1-\alpha )(\delta -1))A_{\alpha }\left(G\right)$ has eigenvalue ${\rho }_{\alpha }^2\left(G\right)-(\alpha \Delta +(1-\alpha )(\delta -1)){\rho }_{\alpha }\left(G\right)$ associated with a nonnegative eigenvector which is also a ${\rho }_{\alpha }\left(G\right)$ eigenvector of $A_{\alpha }\left(G\right)$. By [3],

$${\rho }_{\alpha }^2\left(G\right)-(\alpha \Delta +(1-\alpha )(\delta -1)){\rho }_{\alpha }\left(G\right)\le (1-\alpha )(2m-(n-1)\delta ),$$

with equality if, and only if, the equality in (4) (or equivalently in (3)) holds for every $1\le i\le n.$ Solving the above quadratic inequality of ${\rho }_{\alpha }\left(G\right)$ and studying the equality, the theorem follows. □

Theorem 1 is a generalization of a result of Hong, Shu, and Fang [4]. It is worth mentioning that many different upper bounds of ${\rho }_{\alpha }\left(G\right)$ are already given in [5,6,7].

 Remark 1.

If we give an additional assumption in Theorem 1

$$t:=\underset{i\in V}{min}\sum _{j\ne i,ij\notin E}(d_j-\delta ),$$

then with little modification of the proof in line (3), we have

$${\rho }_{\alpha }\left(G\right)\le \frac{\alpha \Delta +(1-\alpha )(\delta -1)+\sqrt{{(\alpha \Delta +(1-\alpha )(\delta -1))}^2+4(1-\alpha )(2m-(n-1)\delta -t)}}{2}.$$

The above equality holds if, and only if, (i) G is regular, or (ii) $\alpha =0$ and

$$t=\sum _{j\ne i,ij\notin E}(d_j-\delta )fori\in V.$$

(5)

Theorem 1 is a special case of Remark 1 with $t=0$. The following is a graph that satifies (5) with $\delta =2$ and $t=1$. It is of independent interest to find all graphs that satisfy (5).