Laplacian distribution and domination

DOI10.1007/S00373-017-1844-XMaRDI QIDQ1684945zbMATH OpenOpenAlexFDO

Authors David P. Jacobs, Vilmar Trevisan, D. M. Cardoso

Publication date 12 December 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.04482

zbMATH Keywords

domination numberLaplacian eigenvalue

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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)leqgamma(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 $fracgamma(G)m_G[0,1)otinO(logn)$. However, $gamma(G)leq{m}_G[2,n]leq(c+1)gamma(G)$ for $c$-cyclic graphs, $cgeq1$. For trees $T$, $gamma(T)leq{m}_T[2,n]leq2gamma(G)$.

Recommendations

• Domination number and Laplacian eigenvalue distribution
• LAPLACIAN EIGENVALUES OF GRAPHS WITH GIVEN DOMINATION NUMBER
• Minimizing the Laplacian eigenvalues for trees with given domination number
• scientific article; zbMATH DE number 907925
• A note on Laplacian eigenvalues and domination

Cites work

• A linear algorithm for the domination number of a tree
• A relation between the matching number and Laplacian spectrum of a graph
• Domination number and Laplacian eigenvalue distribution
• Domination, packing and excluded minors
• Gallai-type theorems and domination parameters
• Graph-theoretic parameters concerning domination, independence, and irredundance
• scientific article; zbMATH DE number 4130427 (Why is no real title available?)
• scientific article; zbMATH DE number 5844285 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 867649 (Why is no real title available?)
• scientific article; zbMATH DE number 907925 (Why is no real title available?)
• scientific article; zbMATH DE number 3358515 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Interlacing results on matrices associated with graphs
• Irredundance number versus domination number
• Laplace eigenvalues of graphs---a survey
• Laplacian and signless Laplacian spectral radii of graphs with fixed domination number
• On the distribution of Laplacian eigenvalues of trees
• On the hardness of approximating minimization problems
• On the number of Laplacian eigenvalues of trees smaller than two
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY
• The Laplacian Spectrum of a Graph
• Towards a theory of domination in graphs
• Two Bounds for the Domination Number of a Graph
• Vizing's conjecture: a survey and recent results

Cited in

(14)

• Domination number and Laplacian eigenvalue of trees
• Vertex-connectivity, chromatic number, domination number, maximum degree and Laplacian eigenvalue distribution
• Laplacian eigenvalue distribution and graph parameters
• A note on Laplacian eigenvalues and domination
• Domination and spectral graph theory
• Classification of trees by Laplacian eigenvalue distribution and edge covering number
• Proof of a conjecture on distribution of Laplacian eigenvalues and diameter, and beyond
• Signless Laplacian spectrum of a graph
• Laplacian eigenvalue distribution and diameter of graphs
• Distance Laplacian eigenvalues of graphs, and chromatic and independence number
• Diameter vs. Laplacian eigenvalue distribution
• Laplacian eigenvalue distribution in terms of degree sequence
• Laplacian eigenvalue distribution, diameter and domination number of trees
• Domination number and Laplacian eigenvalue distribution

This page was built for publication: Laplacian distribution and domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1684945)