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

Abstract

A relation between the multiplicity m of the second eigenvalue λ₂ 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 λ₂ 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 Verdi´ere’s upper bound on the maximal λ₂-multiplicity, m ≤ chr(_γ(G)) − 1,
where chr(_γ(G)) is the chromatic number and _γ(G) is the genus of G.