Hoffman-type Results for the Sum of k Largest Eigenvalues of a Graph

Shaowei Sun; Mengyao Guo; Hongyan Ge; Kinkar Chandra Das

In the authors' words

Let $S_{k} (G)$ denote the sum of the $k$ largest eigenvalues of a graph $G$ . Motivated by the classical Hoffman program for the spectral radius of a graph, we investigate an additive Hoffman-type problem for $S_{k} (G)$ . For each fixed $k \geq 2$ and sufficiently large order $n$ , we characterize all connected graphs satisfying $S_{k} (G) < 2 k$ . As a consequence, we prove that the path $P_{n}$ is the unique minimizer of $S_{k} (G)$ among all connected graphs of order $n$ . \vspace*{2mm} We further investigate the first Hoffman-type range \[ 2k\leq S_k(G)<2k+\sqrt{2+\sqrt5}-2. \] We completely characterize the non-tree graphs in this range and reduce the tree case to several explicit families. The proofs combine Ky Fan's variational principle, spectral estimates from vertex-disjoint subgraphs, structural results for graphs with small spectral radius, and long-path arguments for bounded-degree graphs.

Main resultLimitation the authors admit

Hoffman-type Results for the Sum of k Largest Eigenvalues of a Graph

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

On infinite families of [Pn​]-irregular graphs

On infinite families of $[P_{n}]$ -irregular graphs