Hoffman's ratio bound

Willem H. Haemers

doi:10.1016/j.laa.2021.02.010

Hoffman's ratio bound

Willem H. Haemers

Econometrics and OR

Research output: Contribution to journal › Article › Scientific › peer-review

30 Citations (Scopus)

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.

Original language	English
Pages (from-to)	215-219
Journal	Linear Algebra and its Applications
Volume	617
DOIs	https://doi.org/10.1016/j.laa.2021.02.010
Publication status	Published - May 2021

Keywords

Clique
Coclique
Eigenvalue
Graph
Hoffman bound
Independence number

Access to Document

10.1016/j.laa.2021.02.010

Cite this

@article{8deb0dca18a44933b7d5322d069bfdd4,

title = "Hoffman's ratio bound",

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.",

keywords = "Clique, Coclique, Eigenvalue, Graph, Hoffman bound, Independence number",

author = "Haemers, {Willem H.}",

year = "2021",

month = may,

doi = "10.1016/j.laa.2021.02.010",

language = "English",

volume = "617",

pages = "215--219",

journal = "Linear Algebra and its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Hoffman's ratio bound

AU - Haemers, Willem H.

PY - 2021/5

Y1 - 2021/5

N2 - 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.

AB - 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.

KW - Clique

KW - Coclique

KW - Eigenvalue

KW - Graph

KW - Hoffman bound

KW - Independence number

U2 - 10.1016/j.laa.2021.02.010

DO - 10.1016/j.laa.2021.02.010

M3 - Article

AN - SCOPUS:85101154707

SN - 0024-3795

VL - 617

SP - 215

EP - 219

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

ER -

Hoffman's ratio bound

Abstract

Keywords

Access to Document

Fingerprint

Cite this