Proof of a conjecture on the $\epsilon$-spectral radius of trees

1.   Introduction

Let $G$ be a simple connected graph with vertex set $V(G) = \{v_1, v_2, \dots, v_n\}$. The distance between vertices $v_i$ and $v_j$ in $G$, denoted by $d_G(v_i, v_j)$, is the length of the shortest path between $v_i$ and $v_j$. The distance matrix of $G$, denoted by $D(G)$, is the $n\times n$ matrix whose $(i, j)$-entry is equal to $d_G(v_i, v_j)$. Let $A(G)$ be the adjacency matrix of $G$. The adjacency matrix and the distance matrix of a graph are well-studied matrix classes in the field of spectral graph theory. For more details about the study of classes of matrices associated with graphs, we refer to ^[2,3,4].

For $u\in V(G)$, $e_G(u)$ or $e(u)$ denotes the eccentricity of $u$ in $G$, which is equal to the largest distance from $u$ to other vertices in $G$. The diameter of a graph $G$, denoted by $diam(G)$, is defined to be the maximum of the eccentricity of all the vertices of $G$. A vertex $v$ is said to be an eccentric vertex of the vertex $u$ if $d_G(u, v) = e(u)$. A vertex $u\in V(G)$ is said to be a diametrical vertex of $G$ if $e(u) = diam(G)$. If each vertex of $G$ is a diametrical vertex and has a unique eccentric vertex, then $G$ is called a diametrical graph.

A matching in $G$ is a set of edges without common vertices. The maximum matching is a matching with the maximum size in $G$. The matching number is the size of a maximum matching in $G$.

The eccentricity matrix of the graph $G$, denoted by $\epsilon(G)$, is defined as ^[14]

It is also known as the DMAX-matrix defined by Randić in ^[10] as a tool for chemical graph theory. The eigenvalues of the eccentricity matrix of a graph $G$ are called the eccentricity eigenvalues, or $\epsilon$-eigenvalues, of $G$. Since $\epsilon(G)$ is symmetric, the $\epsilon$-eigenvalues are all real, which are denoted by $\xi_1(G)\geq \xi_2(G)\geq \dots \geq \xi_n(G)$. As usual, $\xi_1(G)$ is called the $\epsilon$-spectral radius of $G$, denoted also by $\rho_\epsilon(G)$.

Recently, the $\epsilon$-spectral radius has received much attention. Wang et al. ^[13] determined sharp lower and upper bounds for the $\epsilon$-spectral radius of graphs and identified the corresponding extremal graphs. Wei et al. ^[16] determined the $n$-vertex trees with minimum $\epsilon$-spectral radius. Furthermore, in ^[16], the authors identified all trees with given order and diameter having the minimum $\epsilon$-spectral radius. He and Lu ^[5] identified the $n$-vertex trees with fixed odd diameter having the maximum $\epsilon$-spectral radius. Wei, Li and Zhang ^[17] characterized the $n$-vertex trees having the second minimum $\epsilon$-spectral radius and identified the $n$-vertex trees with small matching number having the minimum $\epsilon$-spectral radii. For more advances on the $\epsilon$-eigenvalues, one may be referred to ^{[7,8,9,12,15]}.

Let $\widehat{T}^{a, b}_{n, 5}$ be the $n$-vertex tree obtained from $P_5 = v_1v_2v_3v_4v_5v_6$ by attaching $a$ pendent edges to $v_3$, $b$ pendent edges and a path with length $2$ to $v_4$, where $a, b\ge 1$ and $a+b = n-8$, see Figure 1.

Let $\mathscr{T}_{n, d}$ be the set of trees with order $n$ and diameter $d$. Wei, Li and Zhang ^[17] proved in their Theorem 4.6 that, among the $n$-vertex trees with matching number $5$ in $\bigcup_{d\ne 4}\mathscr{T}_{n, d}$, the tree $\widehat{T}^{1, n-9}_{n, 5}$ has the minimum $\epsilon$-spectral radius if $10 \leq n \leq 16$, and the trees $\widehat{T}^{\lfloor\gamma \rfloor, n-8-\lfloor\gamma \rfloor}_{n, 5}$ or $\widehat{T}^{\lceil\gamma \rceil, n-8-\lceil\gamma \rceil}_{n, 5}$ have the minimum $\epsilon$-spectral radius if $n \geq 17$, where $\gamma = \frac{1}{144}(48n-461-20\sqrt{6n-17})$. They commented that "since it is abnormal for the eccentricity matrices of trees of diameter $4$", their Theorem 4.6 does not solve the problem for $d = 4$. So they proposed the following conjecture.

Conjecture 1.1. Among the $n$-vertex trees with matching number $5$ with $n \geq 10$, the tree $\widehat{T}^{1, n-9}_{n, 5}$ has the minimum $\epsilon$-spectral radius if $10 \leq n \leq 16$, and the trees $\widehat{T}^{\lfloor\gamma \rfloor, n-8-\lfloor\gamma \rfloor}_{n, 5}$ or $\widehat{T}^{\lceil\gamma \rceil, n-8-\lceil\gamma \rceil}_{n, 5}$ have the minimum $\epsilon$-spectral radius if $n \geq 17$, where $\gamma = \frac{1}{144}(48n-461-20\sqrt{6n-17})$.

In this article, to avoid the earlier difficulty, we propose new graph transformations, characterize the certain structures of the extremal trees and determine the unique tree in $\mathscr{T}_{n, 4}$ with matching number $5$ having the minimum $\epsilon$-spectral radius, so give an affirmative answer to the conjecture.

2.   Preliminaries

In this section, we introduce some preliminary results which will be used to in our proofs. The following Lemma is a well-known result in the theory of nonnegative matrices, see ^[4,6].

Lemma 2.1. ^[4,6] Let $A$ and $B$ be two nonnegative irreducible matrices with same order. If $A_{i, j}\leq B_{i, j}$ for each $i, j$, then $\rho(A)\leq \rho(B)$ with equality if and only if $A = B$, where $\rho(A)$ and $\rho(B)$ denote the spectral radius of $A$ and $B$, respectively.

Mahato et al. ^[8] obtained a lower bound for the $\epsilon$-spectral radius of a graph with given diameter, which will be used in the proof of Lemma 3.1 and Lemma 3.2.

Lemma 2.2. If $G$ is a connected graph with diameter $d\geq 2$, then $\xi_{1}(G)\geq d$ with equality if and only if $G$ is a diametrical graph.

Lemma 2.3. ^[14] The eccentricity matrix of a tree with order $n\geq 2$ is irreducible.

Note that for a tree $T$ with at least two vertices, $\epsilon(T)$ is an irreducible nonnegative matrix by Lemma 2.3. Thus by the Perron-Frobenius theorem, $\rho_\epsilon(T)$ is simple, and there is a positive unit eigenvector of $\epsilon(T)$, which is called Perron vector of $\epsilon(T)$, corresponding to $\rho_\epsilon(T)$.

Lemma 2.4. ^[17] $\rho_\epsilon(\widehat{T}^{a, b}_{n, 5})$ is the largest root of $f(\lambda) = 0$, where $f(\lambda) = \lambda^4-32a\lambda^2-16b\lambda^2-$$141\lambda^2+512ab+1312a+800b+2050$.

Lemma 2.5. ^[17] Among $\bigcup_{d\neq4}\mathscr{T}_{n, d}$ with matching number 5, $\widehat{T}^{1, n-9}_{n, 5}$ is the tree with minimum $\epsilon$-spectral radius for $10\leq n\leq16$, and $\widehat{T}^{\lfloor\gamma \rfloor, n-8-\lfloor\gamma \rfloor}_{n, 5}$ or $\widehat{T}^{\lceil\gamma \rceil, n-8-\lceil\gamma \rceil}_{n, 5}$ are trees with the minimum $\epsilon$-spectral radius for $n\geq17$, where $\gamma = \frac{1}{144}(48n-461-20\sqrt{6n-17})$.

3.   Main results

Let $S_{n, \ell}(a_0, a_1, \dots, a_{\ell})$ be the tree obtained by adding an edge between the center $v_0$ of a star $S_{a_0+1}$ and the center $v_i$ of the star $S_{a_i+1}$ for each $i = 1, 2, \dots, \ell$, see Figure 2. Any tree with diameter $4$ is of the form $S_{n, \ell}(a_0, a_1, \dots, a_{\ell})$ with $\ell\geq 2$ and $a_i\geq 1$ for each $i = 1, 2, \dots, \ell$.

Lemma 3.1. Let $T\cong S_{n, \ell}(a_0, a_1, \dots, a_{\ell})$ with $\ell\geq 2$ and $1\leq a_1\leq a_2\leq \dots \leq a_{\ell}$, where $n = l+1+\sum_{k = 0}^{\ell}a_k$. If there exists $k$ such that $1\leq k\leq \ell-1$ and $a_k\geq 2$, then

Proof. Let $U_i = V(S_{a_i+1})\backslash\{v_i\}$ for $0\leq i\leq \ell$. We partition $V(T)$ into $U_0, \{v_0\}, \{v_1\}, ..., \{v_{\ell}\}, U_1, ..., U_{\ell}$, then $\epsilon(T)$ can be written as

Let $x$ be a Perron eigenvector corresponding to $\rho: = \rho_\epsilon(T)$, whose coordinate with respect to vertex $v$ is $x_v$.

Since $\rho x_{u_0} = 3\sum_{j = 1}^{\ell}\sum_{u_j \in U_j}x_{u_j}$ for any $u_0\in U_0$, we have $x_{u_0} = x_{u_0'}$ for any $u_0, u_0'\in U_0$. Similarly, we have $x_{u_j} = x_{u_j}'$ for any $x_{u_j}, x_{u_j}'\in U_{j}$ with $j = 1, 2, ..., \ell$. Thus

By eliminating $x_{u_0}$, $x_{v_0}, \dots x_{v_{\ell}}$ from the above system, we obtain

Let $c = 9a_0+9\ell-14$. Since $x_{u_i} > 0$ for all $1\leq i\leq \ell$, $\rho$ is the largest root of $f_{a_k, a_{\ell}}(\lambda) = 0$, where

By Lemma 2.2, $\rho\geq diam(T) = 4$. Then $\rho^2+4a_i\rho-9a_i > 0$ for all $1\leq i\leq \ell$. Hence, $\rho$ is the largest root of $g_{a_k, a_{\ell}}(\lambda) = 0$, where

Since for $\lambda > 0$,

we have $g_{a_k, a_{\ell}}(\lambda)$ is monotonically increasing for $\lambda > 0$. Thus it is sufficient to prove $g_{a_k-1, a_{\ell}+1}(\lambda) > g_{a_k, a_{\ell}}(\lambda)$ for $\lambda\geq \rho$.

By a direct calculation, one has

Lemma 3.2. Let $T_b = S_{n, 4}(n-8-b, 1, 1, 1, b)$ with $1\leq b\leq n-9$. Then $\rho_\epsilon(T_b)\geq 6+\sqrt{36n-191}$ with equality if and only if $b = 1$.

Proof. By the proof of Lemma 3.1, $\rho_\epsilon(T_b)$ is the largest root of

i.e., $f_b(\lambda) = 0$, where

Note that

By a direct calculation, $\rho_\epsilon(T_1) = 6+\sqrt{36n-191}$.

Suppose now that $2\leq b\leq n-9$. Then it is sufficient to prove $f_1(\lambda) > f_b(\lambda)$ for $\lambda\geq \rho_\epsilon(T_b)$. By a direct calculation, one has

where $g(\lambda) = (9n-9b-29)\lambda^2+(144n-144b-1016)\lambda+9(36b-36n+227)$ with $2\leq b\leq n-9$. By Lemma 2.2, we get $\rho_\epsilon(T_b)\geq diam(T) = 4$. Since $9n-9b-29 = 9(n-b)-29\geq 52 > 0$ and $-\frac{144n-144b-1016}{2(9n-9b-29)} = -\frac{144(n-b)-1016}{2(9n-9b-29)} < 0$, we have $g(\lambda)$ is montoncially increasing for $\lambda > 0$. Then $g(\lambda)\geq g(\rho_\epsilon(T_b))\geq g(4) = 396(n-b-8)+683 > 0$. Thus, $f_1(\lambda) > f_b(\lambda)$ for $\lambda\geq \rho_\epsilon(T_b)$. We note that a similar treatment has been used in studying the Estrada indices, see ^[1,11].

Lemma 3.3. Let $T_1 = S_{n, 4}(n-9, 1, 1, 1, 1)$ and $T_1^* = S_{n, 5}(0, 1, 1, 1, 1, n-10)$. For $n\geq 11$, we have $\rho_\epsilon(T_1^*) > \rho_\epsilon(T_1)$.

Proof. Let $N_{T_1}(v_0)\setminus\{v_1, v_2, v_3, v_4\} = \{w_0, w_1, \dots, w_{n-10}\}$, $N_{T_1}(v_i)\setminus\{v_0\} = \{u_i\}$ for $i = 1, 2, 3, 4$. Then

Let $V_1 = \{u_1, u_2, u_3, u_4\}$, $V_2 = \{v_1, v_2, v_3, v_4\}$ and $V_3 = \{w_1, w_2, \dots, w_{n-10}\}$. As we pass from $T_1$ to $T_1^*$, we have

Thus, $\epsilon(T_1^*) > \epsilon(T_1)$. Since $T_1$ and $T_1^*$ are $n$-vertex trees, by Lemma 2.3, $\epsilon(T_1)$ and $\epsilon(T_1^*)$ are irreducible. By Lemma 2.1, $\rho_\epsilon(T_1^*) > \rho_\epsilon(T_1)$.

Theorem 3.1. Let $T$ be an $n$-vertex tree with diameter 4 and matching number 5. Then $\rho_\epsilon(T)\geq 6+\sqrt{36n-191}$ with equality if and only if $T\cong S_{n, 4}(n-9, 1, 1, 1, 1)$.

Proof. Let $T$ be the tree having minimum $\epsilon$-spectral radius among $n$-vertex trees with diameter $4$ and matching number $5$. Then $T\cong S_{n, \ell}(a_0, a_1, \dots, a_{\ell})$. Since the matching number of $T$ is $5$, $\ell = 4$ for $a_0\geq 1$ and $\ell = 5$ for $a_0 = 0$. Thus, assume that $T\cong S_{n, 4}(a_0, a_1, a_2, a_3, a_4)$ with $a_0\geq 1$ and $1\leq a_1\leq a_2\leq a_3\leq a_4$ or $T\cong S_{n, 5}(0, b_1, b_2, b_3, b_4, b_5)$ with $1\leq b_1\leq b_2\leq b_3\leq b_4\leq b_5$. In the former case, we have by Lemma 3.1 that $a_1 = a_2 = a_3 = 1$, and by Lemma 3.2 that $a_4 = 1$, so $a_0 = n-9$, that is, $T\cong S_{n, 4}(n-9, 1, 1, 1, 1)$. In the latter case, we have by Lemma 3.1 that $b_1 = b_2 = b_3 = b_4 = 1$, so $T\cong S_{n, 5}(0, 1, 1, 1, 1, n-10)$. By Lemma 3.3, $T\cong S_{n, 4}(n-9, 1, 1, 1, 1)$.

Theorem 3.2. Among the $n$-vertex trees with matching number 5 with $n \geq 10$, $\widehat{T}^{1, n-9}_{n, 5}$ is the tree with minimum $\epsilon$-spectral radius for $10\leq n\leq16$, and $\widehat{T}^{\lfloor\gamma \rfloor, n-8-\lfloor\gamma \rfloor}_{n, 5}$ or $\widehat{T}^{\lceil\gamma \rceil, n-8-\lceil\gamma \rceil}_{n, 5}$ are trees with the minimum $\epsilon$-spectral radius for $n\geq17$, where $\gamma = \frac{1}{144}(48n-461-20\sqrt{6n-17})$.

Proof. Let $T$ be the tree minimizing the $\epsilon$-spectral radius in $\mathscr{T}_{n, d}$ with matching number 5. If $d = 4$, then $T\cong S_{n, 4}(n-9, 1, 1, 1, 1)$ by Theorem 3.1. If $d\geq5$, then $T\cong \widehat{T}^{a, b}_{n, 5}$ by Lemma 2.5. Let $\rho_\epsilon$ be the spectral radius of $\widehat{T}^{a, b}_{n, 5}$. Then by Lemma 2.4, $\rho_\epsilon$ is the largest root of $f(\lambda) = 0$, where

Note that $a+b = n-8$. Thus

Since $n\geq10$, then $512a(n-7-a)+800n-4350 > 0$. Thus

Combining with Lemma 2.5, the result follows.

4.   Conclusions

In this contribution, we characterize the unique tree among all trees with diameter $4$ and matching number $5$ that minimizes the $\epsilon$-spectral radius. This confirms a conjecture in ^[17]. By combining the results from ^[17], the trees with minimum $\epsilon$-spectral radius among all trees with matching number $r\leq 5$ have been characterized completely. For further study, one may try to determine the trees with the minimum $\epsilon$-spectral radius among all trees with matching number $r\geq 6$ or even among trees with given fraction matching number.

Acknowledgments

The authors would like to thank anonymous referees for helpful comments and suggestions which improved the original version of the paper. This work was supported by Natural Science Foundation of Guangdong Province (No.2021A1515010028).

Conflict of interest

The authors declare that they have no competing interests.