Back to Search
Start Over
Hoffman's ratio bound
- Source :
- Linear Algebra and its Applications, 617, 215-219. Elsevier Inc.
- Publication Year :
- 2021
- Publisher :
- Elsevier BV, 2021.
-
Abstract
- Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations.
- Subjects :
- Clique
Eigenvalue
010103 numerical & computational mathematics
Clique (graph theory)
01 natural sciences
Upper and lower bounds
Graph
Hoffman bound
Combinatorics
Mathematics::Probability
Computer Science::Discrete Mathematics
FOS: Mathematics
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Adjacency matrix
0101 mathematics
Eigenvalues and eigenvectors
Independence number
Mathematics
Numerical Analysis
Mathematics::Combinatorics
Algebra and Number Theory
010102 general mathematics
Coclique
Black hole
Graph (abstract data type)
Regular graph
Combinatorics (math.CO)
Mathematics::Differential Geometry
Geometry and Topology
Subjects
Details
- ISSN :
- 00243795
- Volume :
- 617
- Database :
- OpenAIRE
- Journal :
- Linear Algebra and its Applications
- Accession number :
- edsair.doi.dedup.....9f5ad39b894b0ae995c86a1be9aba820
- Full Text :
- https://doi.org/10.1016/j.laa.2021.02.010