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 Theory Laplacian eigenvalues Domination 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 - Artigos DMat - Artigos OGTCG - Artigos |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.