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.