Mathematical Conferences Niš, Serbia, 13th Serbian Mathematical Congress

Font Size: 
Graphs with maximal spread in some classes of graphs
Tatjana Aleksic, Miroslav Petrovic

Last modified: 2014-05-06

Abstract


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.\ \mbox{$s(G)=\rho(G)-\lambda(G)$.} Characterising the graph with maximal spread is still a difficult problem. If we restrict the discussion to some classes of connected graphs of a prescribed order and size, we can determine the graphs whose spread is maximal among graphs of certain classes. In this paper, we present a unique graph whose spread is maximal in the class of bicyclic graphs with $n$ vertices. We, also, characterise a unique cactus whose spread is maximal in the class $C(n, k)$ of cacti with $n$ vertices and $k$ cycles. We prove that the obtained graph is a bundle of a special form.