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.