A domain monotonicity theorem for graphs and Hamiltonicity. (English) Zbl 0765.05071

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.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
Full Text: DOI


[1] Alon, N., Eigenvalues and expanders, Combinatorica, 6, 83-96, (1986) · Zbl 0661.05053
[2] Alon, N.; Milman, V.D., Λ_{1}, isoperimetric inequalities for graphs and superconcentrators, J. combin. theory ser. B, 38, 73-88, (1985) · Zbl 0549.05051
[3] Anderson, W.N.; Morley, T.D., Eigenvalues of the Laplacian of a graph, Linear and multilinear algebra, 18, 141-145, (1985) · Zbl 0594.05046
[4] Biggs, N.L., Algebraic graph theory, (1974), Cambridge Univ. Press Cambridge · Zbl 0501.05039
[5] Cvetković, D.M.; Doob, M.; Sachs, H., Spectra of graphs—theory and applications, Spectra of graphs—theory and applications, (1979), Academic Press New York · Zbl 0824.05046
[6] Kel’mans, A.K., Properties of the characteristic polynomial of a graph, (), 27-41, (in Russian)
[7] Lovász, L., On the Shannon capacity of a graph, IEEE trans. inform. theory, 25, 1-7, (1979) · Zbl 0395.94021
[8] Lovász, L., Topological and algebraic methods in graph theory, (), 1-14
[9] Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 261-277, (1988) · Zbl 0661.05035
[10] Mohar, B., Isoperimetric numbers of graphs, J. combin. theory ser. B, 47, 274-291, (1989) · Zbl 0719.05042
[11] Mohar, B., Laplacian spectrum of graphs, (), 871-898 · Zbl 0840.05059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.