Cacti whose spread is maximal (Q489338)

The manuscript deals with the spread of a connected graph. Let \(G=(V,E)\) be a simple graph with vertex set \(V\) and edge set \(E\) and \(A(G)\) the adjacency matrix of \(G\). Let \(G\) be of order \(n=|V|\) and size \(m=|E|\). The largest and the least eigenvalue of \(A(G)\) are denoted by \(\rho(G)\) and \(\lambda(G)\), respectively. The graph's spread \(s(G)\) is defined as the difference between both eigenvalues, i.e. \(s(G)=\rho(G)-\lambda(G)\). A connected graph \(G\) is a cactus if any two of its cycles have at most one common vertex. If all cycles of a cactus \(G\) have exactly one common vertex, then it is called a bundle. Let \({\mathcal C}(n,k)\) denote the class of cacti with \(n\) vertices and \(k\) cycles. In this paper, the authors study the spread of the elements of \({\mathcal C}(n,k)\) and determine a unique graph with the maximal spread in this class. In the same class, \textit{M. Petrović} et al. characterized in [Linear Algebra Appl. 435, No. 9, 2303--2313 (2011; Zbl 1222.05174)] a unique graph whose least eigenvalue is minimal. Now, the authors show that these two graphs are the same except for a few cases in which \(n\) is small. They also prove that the graph with the maximum spread among cacti with \(n\) vertices and \(k\) cycles is a bundle that has a particular form.