ELA, Volume 10, pp. 212-222, August 2003, abstract.
The Merris Index of a Graph
Felix Goldberg and Gregory Shapiro
In this paper the sharpness of an upper bound,
due to Merris, on the independence number of a
graph is investigated. Graphs that attain this
bound are called Merris graphs. Some families
of Merris graphs are found, including Kneser
graphs K(v,2) and non-singular regular bipartite
graphs. For example, the Petersen graph and the
Clebsch graph turn out to be Merris graphs. Some
sufficient conditions for non-Merrisness are
studied in the paper. In particular it is shown
that the only Merris graphs among the joins are
the stars. It is also proved that every graph is
isomorphic to an induced subgraph of a Merris
graph and conjectured that almost all graphs are
not Merris graphs.