Laplacian Distribution and Domination

Let $m_G(I)$ denote the number of Laplacian eigenvalues of a graph $G$ in an interval $I$, and let $γ(G)$ denote its domination number. We extend the recent result $m_G[0,1) \leq γ(G)$, and show that isolate-free graphs also satisfy $γ(G) \leq 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 $γ(G)$, showing that $\frac{γ(G)}{m_G[0,1)} \not\in O(\log n)$. However, $γ(G) \leq m_G[2, n] \leq (c + 1) γ(G)$ for $c$-cyclic graphs, $c \geq 1$. For trees $T$, $γ(T) \leq m_T[2, n] \leq 2 γ(G)$.

No reviews yet.

No comments yet.