ELA, Volume 16, pp. 315-324, October 2007, abstract.

A Relation Between the Multiplicity of the Second Eigenvalue 
of a Graph Laplacian, Courant's Nodal Line Theorem and the 
Substantial Dimension of Tight Polyhedral Surfaces

Tsvi Tlusty

A relation between the multiplicity m of the second eigenvalue 
lambda_2 of a Laplacian on a graph G, tight mappings of G and a 
discrete analogue of Courant's nodal line theorem is discussed. 
For a certain class of graphs, it is shown that the m-dimensional 
eigenspace of lambda_2 is tight and thus defines a tight mapping 
of G into an m-dimensional Euclidean space. The tightness of the 
mapping is shown to set Colin de Verdiere's upper bound on the 
maximal lambda_2-multiplicity, m <= chr[gamma(G)]-1, where
chr[gamma(G)] is the chromatic number and gamma(G) is the
genus of G.