Cacti Whose Spread is Maximal

Abstract

© 2013, Springer Japan. For a simple graph G, the graph’s spread s(G) is defined as the difference between the largest eigenvalue and the least eigenvalue of the graph’s adjacency matrix, i.e. (formula presented) (formula presented). A connected graph G is a cactus if any two of its cycles have at most one common vertex. If all cycles of the cactus G have exactly one common vertex then it is called a bundle. Let (formula presented) denote the class of cacti with n vertices and k cycles. In this paper, we determine a unique cactus whose spread is maximal among the cacti with n vertices and k cycles. We prove that the obtained graph is a bundle of a special form. Within the class (formula presented) (formula presented) we also present a unique cactus whose least eigenvalue is minimal (Petrović et al. in Linear Algebra Appl 435:2357–2364, 2011) and show that these two graphs are the same, except for a few cases in which n is small.