Signless Laplacians of finite graphs. (English) Zbl 1113.05061

Čvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan K.

Linear Algebra Appl. 423, No. 1, 155-171 (2007).

Summary: We survey properties of spectra of signless Laplacians of graphs and discuss possibilities for developing a spectral theory of graphs based on this matrix. For regular graphs the whole existing theory of spectra of the adjacency matrix and of the Laplacian matrix transfers directly to the signless Laplacian, and so we consider arbitrary graphs with special emphasis on the non-regular case. The results which we survey (old and new) are of two types: (a) results obtained by applying to the signless Laplacian the same reasoning as for corresponding results concerning the adjacency matrix, (b) results obtained indirectly via line graphs. Among other things, we present eigenvalue bounds for several graph invariants, an interpretation of the coefficients of the characteristic polynomial, a theorem on powers of the signless Laplacian and some remarks on star complements.

MSC:

05C50

Graphs and linear algebra (matrices, eigenvalues, etc.)

Keywords:

graph spectra; line graph; signless Laplacian; star complement

References:

[1]	Chen, Y., Properties of spectra of graphs and line graphs, Appl. math. J. Chinese univ. ser. B, 17, 3, 371-376, (2002) · Zbl 1022.05046
[2]	Cvetković, D., Graphs with least eigenvalue −2: the eigenspace of the eigenvalue −2, Rendiconti sem. mat. messina, ser. II, 25, 9, 63-86, (2003) · Zbl 1124.05061
[3]	Cvetković, D., Signless Laplacians and line graphs, Bull. acad. serbe sci. arts, cl. sci. math. natur., sci. math., 131, 30, 85-92, (2005) · Zbl 1119.05066
[4]	Cvetković, D.; Doob, M.; Sachs, H., Spectra of graphs, (1995), Johann Ambrosius Barth Verlag Heidelberg-Leipzig · Zbl 0824.05046
[5]	Cvetković, D.; Lepović, M., Cospectral graphs with least eigenvalue at least −2, Publ. inst. math. (beograd), 78, 92, 51-63, (2005) · Zbl 1265.05358
[6]	Cvetković, D.; Rowlinson, P.; Simić, S., Eigenspaces of graphs, (1997), Cambridge University Press Cambridge · Zbl 0878.05057
[7]	Cvetković, D.; Rowlinson, P.; Simić, S., Spectral generalizations of line graphs, on graphs with least eigenvalue −2, (2004), Cambridge University Press Cambridge · Zbl 1061.05057
[8]	van Dam, E.R.; Haemers, W., Which graphs are determined by their spectrum?, Linear algebra appl., 373, 241-272, (2003) · Zbl 1026.05079
[9]	Dedo, E., La reconstruibilita del polinomio carrateristico del comutato di un grafo, Boll. unione mat. ital., 18A, 5, 423-429, (1981) · Zbl 0481.05050
[10]	Desai, M.; Rao, V., A characterization of the smallest eigenvalue of a graph, J. graph theory, 18, 181-194, (1994) · Zbl 0792.05096
[11]	Faria, I., Permanental roots and the star degree of a graph, Linear algebra appl., 64, 255-265, (1985) · Zbl 0559.05041
[12]	Gantmacher, F.R., Theory of matrices I, II, (1960), Chelsea New York · Zbl 0088.25103
[13]	Grone, R.; Merris, R.; Sunder, V.S., The Laplacian spectrum of a graph, SIAM J. matrix anal. appl., 11, 218-238, (1990) · Zbl 0733.05060
[14]	Gutman, I.; Cvetković, D., Relations between graphs and special functions, Univ. kragujevac, coll. sci. papers, fac. sci., 1, 101-119, (1980)
[15]	Haemers, W.; Spence, E., Enumeration of cospectral graphs, Europ. J. comb., 25, 199-211, (2004) · Zbl 1033.05070
[16]	Lihtenbaum, L.M., A duality theorem for simple graphs, Usp. mat. nauk., 18, 5, 185-190, (1958), (Russian)
[17]	Lihtenbaum, L.M., Traces of powers of the vertex- and edge-neighbourhood matrix of a simple graph (Russian), Izv. viss. ucebn. zav. mat., 5, 154-163, (1959)
[18]	Rowlinson, P., Star complements in finite graphs: a survey, Rendiconti sem. mat. messina, 8, 145-162, (2002) · Zbl 1042.05061
[19]	Simić, S.K.; Li Marzi, E.M.; Belardo, F., Connected graphs of fixed order and size with maximal index: structural considerations, Le matematiche, 59, 1-2, 349-365, (2004) · Zbl 1195.05045
[20]	Vahovskiiˇ, E.V., On the eigenvalues of the neighbourhood matrix of simple graphs (Russian), Sibir. mat. J., 6, 44-49, (1965)