Stability of nodal structures in graph eigenfunctions and its relation to the nodal domain count

The nodal domains of eigenvectors of the discrete Schrödinger operator on simple, finite and connected graphs are considered. Courant's well-known nodal domain theorem applies in the present case, and sets an upper bound to the number of nodal domains of eigenvectors: arranging the spectrum as a non-decreasing sequence, and denoting by νn the number of nodal domains of the nth eigenvector, Courant's theorem guarantees that the nodal deficiency n − νn is non-negative. (The above applies for generic eigenvectors. Special care should be exercised for eigenvectors with vanishing components.) The main result of this work is that the nodal deficiency for generic eigenvectors is equal to a Morse index of an energy functional whose value at its relevant critical points coincides with the eigenvalue. The association of the nodal deficiency to the stability of an energy functional at its critical points was recently discussed in the context of quantum graphs Band et al (2011 Commun. Math. Phys. at press (doi:10.1007/s00220-011-1384-9)) and Dirichlet Laplacian in bounded domains in $\mathbb {R}^d$ Berkolaiko et al (2011 arXiv:1107.3489). This work adapts this result to the discrete case. The definition of the energy functional in the discrete case requires a special setting, substantially different from the one used in Band et al and Berkolaiko et al and it is presented here in detail