×

Towards a spectral theory of graphs based on the signless Laplacian. I. (English) Zbl 1224.05293

Spectral graph theory tries to exploit numerous relations between graphs and matrices in order to study problems of graphs by means of eigenvalues of some graph matrices. There are several graph matrices which can be used for this purpose and there are several such theories.
For a given graph \(G\), the matrix \(Q=D+A\) is called the signless Laplacian, where \(A\) is the adjacency matrix and \(D\) is the diagonal matrix of vertex degree. The title of this paper indicates the intention to build a spectral graph theory based on the signless Laplacian. Since the signless Laplacian spectrum performs better also in comparison to spectra of other commonly used graph matrices, the signless Laplacian seems to be the most convenient for use in studying graph properties. Connection with spectra of line graphs and existence of a well developed theory of graphs with least eigenvalue \(-2\) were used as additional arguments for studying eigenvalues of the signless Laplacian.
A new spectral theory of graphs based on the signless Laplacian is called \(Q\)-theory. This paper presents the main spectral theories, including \(Q\)-theory and their interactions. It contains several comparisons of the effectiveness of solving various classes of problems within spectral theories with an emphasis on the performance of the \(Q\)-theory. Results on graph operations, inequalities for eigenvalues and reconstruction problems are given.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C76 Graph operations (line graphs, products, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI