A domain monotonicity theorem for graphs and Hamiltonicity (Q1192950)

The eigenvalues of the Laplacian matrix \(L=[L_{uv}]\) of a graph \((L_{vv}\) is the degree of the vertex \(v\) while \(L_{uv}\) is minus the number of edges between vertices \(u\) and \(v\) for \(u\neq v)\) are studied. Two theorems, which relate the eigenvalues of (the Laplacian matrix of) a graph and the eigenvalues of its induced subgraphs, are proved. A necessary condition for the existence of long cycles in a graph which involves the Laplacian spectrum is derived. As an example, it is proved, by such spectral methods, that the Petersen graph is not Hamiltonian.