Universal winners in trees (Q6932162)

This paper contributes significant results in a very specialized area of spectral graph theory concerning the behavior of the spectral radius under rank-one perturbations of adjacency matrices. In particular, this paper studies the notion of winner and universal winner indices for nonnegative irreducible matrices. For \(A \in M_n,\) \(E_{ii}=e_i e^t_i\) where \(e_i\) is the \(i\)-th standard basis vector and \(t>0\), an index \(p \in [n]\) is called a winner if\N\[\N\rho(A+tE_{pp})=\max_{i\in[n]}\rho(A+tE_{ii}),\N\]\Nand a universal winner if this holds for all \(t>0\).\N\NIn 1994 [\textit{C. R. Johnson} et al., Linear Algebra Appl. 212--213, 415--435 (1994; Zbl 0815.15020)], the problem of minimizing \(\rho(A + D)\), was introduced, where \(D \in S\), and \(S\) is the set of all diagonal matrices \(D \in M_n\) with trace zero. For a fixed trace \(t>0\), it is known that the spectral radius of \(A+D\) is maximized when \(D=tE_{ii}\), leading to the notion of a winner index, which may depend on \(t\). In particular, the concept of universal winner indices that remain winners for all \(t>0\) has been introduced and explored recently.\N\NLet \(G\) be a graph; the set of winners of \(G\) coincides with that of its corona \(G\circ K_1\). \N\NThe most important results are: \N\NTheorem 2.7. Let \(A \ge 0\) be irreducible. Then there exists an interval \((t_1,t_2)\subset(0,\infty)\) such that, for each \(t\in(t_1,t_2)\),\N\[\N\rho\!\left(A+tE_{ii}\right) > \rho\!\left(A+tE_{jj}\right)\N\]\Nif and only if the value of the characteristic polynomial \(\varphi\!\left(A(i\mid i),\lambda\right)\) of the principal submatrix \(A(i\mid i)\) is larger than that of \(\varphi\!\left(A(j\mid j),\lambda\right)\) for some \(\lambda > \rho(A)\). \N\NLet \(T\) be a tree on \(n\) vertices and let \(v\) be a vertex of \(T\) with maximum degree. Let \(k\) be an integer such that\N\[\Nk > \max\{5,\deg(v)+1\}.\N\]\NWe construct a new tree \(T_{n,k}\) as follows:\N\begin{itemize}\N\item[1.] Take the path \(P_{2n+1} = [u_1,\ldots,u_{2n+1}]\) on \(2n+1\) vertices.\N\item[2.] Identify the root vertex of \(B_{k,3}\) with \(u_1\), and identify the vertex \(v\) of \(T\) with \(u_{n+1}\).\N\item[3.] Add \(k+1\) new pendent vertices, each adjacent to \(u_{2n+1}\).\N\end{itemize}\NTheorem 3.5. Let \(n,k\) be positive integers, and let \(T_{n,k}\) be the tree defined above. Then \(T_{n,k}\) has no universal winner. \N\NTheorem 3.9. Suppose that \(d\) and \(k\) are integers satisfying\N\[\Nd+2 > 2k > 2.\N\]\NLet \(S_{d+1}\) and \(S_{k+1}\) denote the star graphs on \(d+1\) and \(k+1\) vertices, respectively. Let \(T\) be the tree obtained by taking one copy of \(S_{k+1}\) and \(k\) copies of \(S_{d+1}\), and then joining the \(i\)-th pendent vertex of \(S_{k+1}\) to the central vertex of the \(i\)-th copy of \(S_{d+1}\). Then the vertices of maximum degree are the only universal winners in \(T\). \N\NLet \(G\) and \(H\) be two graphs on disjoint vertex sets of sizes \(n\) and \(m\), respectively. The corona \(G \circ H\) is defined as the graph obtained by taking one copy of \(G\) and \(n\) copies of \(H\), and then joining the \(i\)-th vertex of \(G\) to every vertex in the \(i\)-th copy of \(H\).\N\NLemma 4.3. Let \(H\) be a connected graph on \(n\) vertices, and let \(G\) be the graph obtained by appending a path of length \(k\) to each vertex of \(H\). Consider the path \(P_{k+1,\rho(H)}\) on \(k+1\) vertices with a loop of weight \(\rho(H)\) at one end vertex. Then the spectral radius of \(G\) is equal to that of \(P_{k+1,\rho(H)}\).