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.


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.