Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/18682
 Title: Laplacian distribution and Ddomination Author: Cardoso, Domingos M.Jacobs, David P.Trevisan, Vilmar Keywords: Spectral Graph TheoryLaplacian eigenvaluesDomination number Issue Date: 29-Oct-2017 Publisher: Springer 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) \leq \gamma(G)$, and show that isolate-free graphs also satisfy $\gamma(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 $\gamma(G)$, showing that $\frac{\gamma(G)}{m_G[0,1)} \not\in O(\log n)$. However, $\gamma(G) \leq m_G[2, n] \leq (c + 1) \dom{G}$ for $c$-cyclic graphs, $c \geq 1$. For trees $T$, $\gamma(T) \leq m_T[2, n] < 2 \gamma(G)$. Peer review: yes URI: http://hdl.handle.net/10773/18682 DOI: 10.1007/s00373-017-1844-x ISSN: 0911-0119 Appears in Collections: CIDMA - ArtigosDMat - ArtigosOGTCG - Artigos

Files in This Item:
There are no files associated with this item.