On Connected Graphs with Maximal Index

D. Cvetković, P. Rowlinson

Let ${\Cal H}(n,n+k)$ denote the set of all connected graps having $n$ vertices and $n+k$ edges ($k\geq 0$). The graphs in ${\Cal H}(n,n+k)$ with maximal index are determined (i) for certain small values of $n$ and $k$, (ii) for arbitrary fixed $k$ and large enough $n$. The results include a proof of a conjecture of Brualdi and Solheid [1].