Laplacian spectral bounds for clique and independence numbers of graphs

DOI10.1016/j.jctb.2006.12.003zbMath1122.05072OpenAlexW2030120460MaRDI QIDQ2642010

Mei Lu, Huiqing Liu, Feng Tian

Publication date: 20 August 2007

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2006.12.003

zbMATH Keywords

independence numberLaplacian spectrumclique number

Mathematics Subject Classification ID

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

Related Items

The Laplacian spread of graphs, Toughness and normalized Laplacian eigenvalues of graphs, On the Aα-spectral radius of connected graphs, Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs, Spectral Bounds for the k-Regular Induced Subgraph Problem, Topological multiplicity of the maximum eigenvalue of graph \(1\)-Laplacian, Spectral radius of digraphs with given dichromatic number, Edge-connectivity and (signless) Laplacian eigenvalue of graphs, Dimension-free bounds and structural results in communication complexity, Graph toughness from Laplacian eigenvalues, The \(A_{\alpha}\) spectral radius characterization of some digraphs, Eigenvalue bounds for independent sets, Bounds on the spectral radius of general hypergraphs in terms of clique number, A simpler characterization of a spectral lower bound on the clique number, Some results on the bounds of signless Laplacian eigenvalues, The \(k\)-regular induced subgraph problem, The maximum clique and the signless Laplacian eigenvalues, The minimum spectral radius of graphs with a given independence number, The spectral radius of graphs with given independence number, More spectral bounds on the clique and independence numbers, A relative bound for independence, Bounds for the Laplacian spectral radius of graphs, The maximum spectral radius of non-bipartite graphs forbidding short odd cycles, GRAPHS WITH SMALL INDEPENDENCE NUMBER MINIMIZING THE SPECTRAL RADIUS

Cites Work

• Eigenvalue bounds for independent sets
• Spectral bounds for the clique and independence numbers of graphs
• An always nontrivial upper bound for Laplacian graph eigenvalues
• Interlacing eigenvalues and graphs
• Isoperimetric numbers of graphs
• Diameters and Eigenvalues
• The Laplacian Spectrum of a Graph II
• An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item