TOWARDS A SPECTRAL THEORY OF GRAPHS BASED ON THE SIGNLESS LAPLACIAN, I

Dragos Cvetkovic and Slobodan K. Simic

Abstract: A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix $M$ which is in a prescribed way defined for any graph. This theory is called $M$-\emph{theory}. We outline a spectral theory of graphs based on the signless Laplacians $Q$ and compare it with other spectral theories, in particular with those based on the adjacency matrix $A$ and the Laplacian $L$. The $Q$-theory can be composed using various connections to other theories: equivalency with $A$-theory and $L$-theory for regular graphs, or with $L$-theory for bipartite graphs, general analogies with $A$-theory and analogies with $A$-theory via line graphs and subdivision graphs. We present results on graph operations, inequalities for eigenvalues and reconstruction problems.

Keywords: graph theory; graph spectra; adjacency matrix; signless Laplacian

Classification (MSC2000): 05C50

Full text of the article: (for faster download, first choose a mirror)

• Compressed DVI file (36 kilobytes)
• Compressed PostScript file (396 kilobytes)
• PDF file (436 kilobytes)