Combinatorial upper bounds for the smallest eigenvalue of a graph

DOI10.1007/S00013-024-01998-8MaRDI QIDQ6564137zbMATH OpenFDO

Authors Aryan Esmailpour, Sara Saeedi Madani, Dariush Kiani

Publication date 28 June 2024

Published in Archiv der Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00013-024-01998-8

zbMATH Keywords

average degreechromatic numbergraph eigenvaluesindependence number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Review text

Let \(G\) be a graph, and let \(\lambda(G)\) denote the smallest eigenvalue of \(G\). In this paper, the authors first provide an upper bound for \(\lambda(G)\) based on induced bipartite subgraphs of \(G\). Consequently, the authors extract two other upper bounds, one relying on the average degrees of induced bipartite subgraphs and a more explicit one in terms of the chromatic number and the independence number of \(G\). In particular, motivated by their bounds, the authors introduce two graph invariants that were of interest on their own. Finally, special attention goes to the investigation of the sharpness of our bounds in various classes of graphs as well as the comparison with an existing well-known upper bound. This is a very interesting paper.

Recommendations

• Some new bounds on the spectral radius of graphs
• A note on \(\lambda_2\) and \(\lambda_n\) of a graph
• A note on eigenvalue bounds for independence numbers of non-regular graphs
• Eigenvalue comparisons in graph theory
• A generalization for the clique and independence numbers

Cites work

• An introduction to the theory of graph spectra
• Bipartite Subgraphs and the Smallest Eigenvalue
• Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph
• Dense induced bipartite subgraphs in triangle-free graphs
• Graphs for which the least eigenvalue is minimal. I
• Graphs for which the least eigenvalue is minimal. II.
• Graphs with maximum degree 17 and maximum average degree less than 3 are list 2-distance ( +2)-colorable
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Max k-cut and the smallest eigenvalue
• Max cut and the smallest eigenvalue
• Optimization, approximation, and complexity classes
• Some observations on the smallest adjacency eigenvalue of a graph
• Spectra of graphs
• The smallest eigenvalue of \(K_{r}\)-free graphs
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• The spectral radius and the maximum degree of irregular graphs
• The spectral radius of subgraphs of regular graphs

Cited in

(1)

• A lower bound for the smallest eigenvalue of a graph and an application to the associahedron graph

This page was built for publication: Combinatorial upper bounds for the smallest eigenvalue of a graph

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