Geodesic
The Merris index of a graph
The electronic journal of linear algebra, Tome 10 (2003), pp. 212-222.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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.
Classification : 05C50, 05C69, 15A42
Keywords: Laplacian matrix, Laplacian eigenvalues, merris index, merris graph, independence number 
@article{ELA_2003__10__a8,
     author = {Goldberg, Felix and Shapiro, Gregory},
     title = {The {Merris} index of a graph},
     journal = {The electronic journal of linear algebra},
     pages = {212--222},
     publisher = {mathdoc},
     volume = {10},
     year = {2003},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ELA_2003__10__a8/}
}
TY  - JOUR
AU  - Goldberg, Felix
AU  - Shapiro, Gregory
TI  - The Merris index of a graph
JO  - The electronic journal of linear algebra
PY  - 2003
SP  - 212
EP  - 222
VL  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ELA_2003__10__a8/
LA  - en
ID  - ELA_2003__10__a8
ER  - 
%0 Journal Article
%A Goldberg, Felix
%A Shapiro, Gregory
%T The Merris index of a graph
%J The electronic journal of linear algebra
%D 2003
%P 212-222
%V 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ELA_2003__10__a8/
%G en
%F ELA_2003__10__a8
Goldberg, Felix; Shapiro, Gregory. The Merris index of a graph. The electronic journal of linear algebra, Tome 10 (2003), pp. 212-222. http://geodesic.mathdoc.fr/item/ELA_2003__10__a8/