An upperbound for the independence and covering number, in terms of eigenvalues.
by
Cyriel Van Nuffelen
University of Antwerp
Coauthors: Kristel Van Rompay (University of Antwerp)

If \alpha(G) is the independence number of a connected graph G, then we have

\alpha(G) <= min[N_G(\lambda >= 0), N_G(\lambda <= 0)], where N_G(\lambda >= 0) denotes the number of non-negative eigenvalues of the adjacency matrix of G.

If \theta(G) is the covering number of a connected graph G, then we conjecture that \theta(G) <= N_G(\lambda > -1).

This conjecture is related to a conjecture of Hoffman, for which we have a counterexample. Translated to \theta, this conjecture stated that \theta(G) <= N_{[`G]</sub>(\lambda <= -1) + 1, where N<sub>[`G]}(\lambda <= -1) denotes the number of eigenvalues of the complentary graph [`G].

Date received: February 15, 2001