Universal winners in trees
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)}\).
- Bounding the largest eigenvalue of trees in terms of the largest vertex degree
- Convergent nonnegative matrices and iterative methods for consistent linear systems
- Derivatives and Perturbations of Eigenvectors
- Derivatives of the spectral radius as a function of non-negative matrix elements
- Dominant eigenvalue and universal winners of digraphs
- Dominant eigenvalues under trace-preserving diagonal perturbations
- Graph theoretic aspects of maximizing the spectral radius of nonnegative matrices
- Handbook of product graphs
- scientific article; zbMATH DE number 3482387 (Why is no real title available?)
- scientific article; zbMATH DE number 734901 (Why is no real title available?)
- Maximizing the spectral radius of fixed trace diagonal perturbations of nonnegative matrices
- Minimization of norms and the spectral radius of a sum of nonnegative matrices under diagonal equivalence
- On the effect of the perturbation of a nonnegative matrix on its Perron eigenvector
- On the first and second order derivatives of the Perron vector
- Spectral Radii of Fixed Frobenius Norm Perturbations of Nonnegative Matrices
- The Spectrum of the Corona of Two Graphs
This page was built for publication: Universal winners in trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6932162)
