<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue4" %>
A Note on a Theorem of Horst Sachs
AndreasW.M. Dress1 and Dragan Stevanović2,3
1Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22-26, 04103 Leipzig Germany
2Faculty of Science and Mathematics, University of Niš, Višegradska 33, 18000 Nis, Serbia and Montenegro
3Faculty of Economics, University of Belgrade, Kamenička 6, 11000 Belgrade, Serbia and Montenegro
Annals of Combinatorics 8 (4) p.487-497 December, 2004
AMS Subject Classification: 05C50
In this note, we present an apparently new and rather short proof of a celebrated theorem of Horst Sachs characterizing bipartite finite graphs in term of their eigenvalue spectrum. Moreover, the simplicity of the proof allows us to establish this theorem and related results as a special instance of much more general assertions regarding the spectral theory of "compact graphs". Finally, some intriguing possible generalizations to locally finite, yet not "compact" graphs suggested by Horst Sachs are discussed in the last section.
Keywords: bipartite graphs, eigenvalues of graphs, compact graphs, locally finite graphs, harmonic graphs, semiharmonic graphs


1. B. Borovicanin, S. Grünewald, I. Gutman, and M. Petrovic, Harmonic graphs with small number of cycles, Discrete Math. 265 (2003) 31--44.

2. D. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs—Theory and Application, Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995.

3. D. Cvetkovic, P. Rowlinson, and S. Simic, Eigenspaces of Graphs, Cambridge University Press, Cambridge, 1997.

4. A. Dress and S. Grünewald, Semiharmonic trees and monocyclic graphs, Appl. Math. Lett. 16 (2003) 1329--1332.

5. A. Dress, S. Grünewald, and D. Stevanovic, Semiharmonic graphs with fixed cyclomatic number, Appl. Math. Lett. 17 (2004) 623--629.

6. A. Dress and I. Gutman, The number of walks in graphs, Appl. Math. Lett. 16 (2003), 797--801.

7. A. Dress and I. Gutman, Asymptotic results regarding the number of walks in a graph, Appl. Math. Lett. 16 (2003) 389--393.

8. S. Grünewald, Harmonic trees, Appl. Math. Lett. 15 (2002) 1001--1004.

9. S. Grünewald and D. Stevanovic, Semiharmonic bicyclic graphs, Appl. Math. Lett., to appear.

10. S. Grünewald and D. Stevanovic, Semiharmonic bicyclic graphs, FSPM Technical Report.

11. A.J. Hoffman, On the polynomial of a graph, Amer. Math. Monthly 70 (1963) 30--36.

12. H. Sachs, Beziehungen zwischen den in einem Graphen enthalteten Kreisen und seinem charakteristischen Polynom, Publ. Math. Debrecen 11 (1964) 119--134.