Laplacian Eigenvalues and the Excess of a Graph

Abstract

In this work, \(\Gamma\) denotes a finite, simple, and connected graph. The \(k\)-excess \(e_k(H)\) of a set \(H \subseteq V(\Gamma)\) is defined as the cardinality of the set of vertices that are at distance greater than \(k\) from \(H\), and the \(k\)-excess \(e_k(h)\) of all \(A\)-subsets of vertices is defined as

\[e_k(h) = \max_{H \subset V(\Gamma),|H|=h} \{ e_k(H) \}\]

The \(k\)-excess \(e_k\) of the graph is obtained from \(e_k(h)\) when \(h = 1\). Here we obtain upper bounds for \(e_k(h)\) and \(e_k\) in terms of the Laplacian eigenvalues of \(\Gamma\).