Laplacian Distribution and Domination

Abstract

Let $m_G(I)$ denote the number of Laplacian eigenvalues of a graph $G$ in an interval $I$, and let $\gamma (G)$ denote its domination number. We extend the recent result $m_G[0,1)\le \gamma (G)$, and show that isolate-free graphs also satisfy $\gamma (G)\le m_G[2,n]$. In pursuit of better understanding Laplacian eigenvalue distribution, we find applications for these inequalities. We relate these spectral parameters with the approximability of $\gamma (G)$, showing that $\frac{\gamma (G)}{m_G[0,1)}\notin O(\log n)$. However, $\gamma (G)\le m_G[2,n]\le (c+1)\gamma (G)$ for $c$-cyclic graphs, $c\ge 1$. For trees $T$, $\gamma (T)\le m_T[2,n]\le 2\gamma (G)$.