The nodal domains of eigenvectors of the discrete Schrodinger 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 $\nu_n$ the number of nodal domains of the
$n$'th eigenvector, Courant's theorem guarantees that the nodal deficiency
$n-\nu_n$ is non negative. (The above applies for generic eigenvectors.
Courant theorem provides an upper bound for the number of nodal domains of
eigenfunctions of a wide class of Laplacian-type operators. In particular, it
holds for generic eigenfunctions of quantum graph. The theorem stipulates that,
after ordering the eigenvalues as a non decreasing sequence, the number of
nodal domains $\nu_n$ of the $n$-th eigenfunction satisfies $n\ge \nu_n$. Here,
we provide a new interpretation for the Courant nodal deficiency $d_n =
n-\nu_n$ in the case of quantum graphs.
Trace formulae for d-regular graphs are derived and used to express the
spectral density in terms of the periodic walks on the graphs under
consideration. The trace formulae depend on a parameter w which can be tuned
continuously to assign different weights to different periodic orbit
contributions. At the special value w=1, the only periodic orbits which
contribute are the non back- scattering orbits, and the smooth part in the
trace formula coincides with the Kesten-McKay expression.