Extremal problems on linear combinations of graph eigenvalues

We study extremal problems for linear combinations of eigenvalues of matrices associated with graphs, with emphasis on quantities involving the spectral radius and the algebraic connectivity. For 0 ≤ α < 1 , define A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) , and let λ 1 ( α ) ( G ) and a ( G ) denote the largest eigenvalue and algebraic connectivity of G , respectively. We prove that, for every fixed 0 ≤ α < 1 and 0 < β ≤ 1 , the quantity λ 1 ( α ) ( G ) − β a ( G ) is uniquely maximized, among all connected graphs of sufficiently large order n , by the kite graph K i n , n − 1 . Here, the kite graph K i n , n − 1 is the graph obtained by attaching a pendant vertex to a complete graph on n − 1 vertices. This gives confirmations of a conjecture of Aouchiche on λ 1 ( G ) − a ( G ) and of the upper-bound part of a conjecture of Hansen and Lucas on q 1 ( G ) − a ( G ) ; it also recovers corresponding extremal results involving vertex connectivity, edge connectivity, and minimum degree. We further prove that, for every connected graph G of order n ≥ 3 ⋅ 2 17 , q 1 ( G ) − a ( G ) ≥ 2 + 2 cos ⁡ 2 π n , with equality if and only if G ≅ C n . This confirms the lower-bound part of the Hansen–Lucas conjecture for large n .