×

Merging the \(A\)- and \(Q\)-spectral theories. (English) Zbl 1499.05384

Summary: Let \(G\) be a graph with adjacency matrix \(A(G)\), and let \(D(G)\) be the diagonal matrix of the degrees of \(G\). The signless Laplacian \(Q(G)\) of \(G\) is defined as \(Q(G) :=A(G) +D(G)\). Cvetković called the study of the adjacency matrix the \(A\)-spectral theory, and the study of the signless Laplacian – the \(Q\)-spectral theory. To track the gradual change of \(A(G)\) into \(Q(G)\), in this paper it is suggested to study the convex linear combinations \(A_\alpha(G)\) of \(A(G)\) and \(D(G)\) defined by \[ A_\alpha (G) :=\alpha D(G) + (1-\alpha)A(G), \quad 0 \leq \alpha \leq 1. \] This study sheds new light on \(A(G)\) and \(Q(G)\), and yields, in particular, a novel spectral Turán theorem. Several open problems are discussed.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A42 Inequalities involving eigenvalues and eigenvectors

References:

[1] N.M.M. de Abreu, V. Nikiforov, Maxima of the Q-index: abstract graph properties, Electron. J. Linear Algebra 23 (2012), 782-789. · Zbl 1252.05116
[2] N.M.M. de Abreu, V. Nikiforov, Maxima of the Q-index: Graphs with bounded clique number, Electron. J. Linear Algebra 24 (2013), 121-130. · Zbl 1282.05165
[3] B. Bollobás, Extremal Graph Theory, Academic Press Inc., London-New York, 1978, xx+488 pp. · Zbl 1099.05044
[4] D. Cvetković, Spectral theory of graphs based on the signless Laplacian, Research Report, (2010), available at: http://www.mi.sanu.ac.rs/projects/signless L reportApr11.pdf
[5] D. Cvetković, Signless Laplacians and line graphs, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Natur., Sci. Math. 131 (2005), 85-92. · Zbl 1119.05066
[6] D. Cvetković, New theorems for signless Laplacians eigenvalues, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Natur., Sci. Math. 137 (2008), 131-146. · Zbl 1199.05212
[7] D. Cvetković, S.K. Simić, Towards a spectral theory of graphs based on the signless Laplacian I, Publ. Inst. Math. (Beograd) 85(99) (2009), 19-33. · Zbl 1224.05293
[8] D. Cvetković, S.K. Simić, Towards a spectral theory of graphs based on the signless Laplacian II, Linear Algebra Appl. 432 (2010), 2257-2272. · Zbl 1218.05089
[9] D. Cvetković, S.K. Simić, Towards a spectral theory of graphs based on the signless Laplacian III, Appl. Anal. Discrete Math. 4 (2010), 156-166. · Zbl 1265.05360
[10] E.R. van Dam, W. Haemers, Which graphs are determined by their spectrum?, Linear Algebra Appl. 373 (2003), 241-272. · Zbl 1026.05079
[11] K.C. Das, On conjectures involving second largest signless Laplacian eigenvalue of graphs, Linear Algebra Appl. 432 (2010), 3018-3029. · Zbl 1195.05040
[12] M. Desai, V. Rao, A characterization of the smallest eigenvalue of a graph, J. Graph Theory 18 (1994), 181-194. · Zbl 0792.05096
[13] L. Feng, G. Yu, On three conjectures involving the signless laplacian spectral radius of graphs, Publ. Inst. Math. (Beograd) (N.S.) 85 (2009), 35-38. · Zbl 1265.05365
[14] H.J. Finck and G. Grohmann, Vollständiges Produkt, chromatische Zahl und charak-teristisches Polynom regulärer Graphen. I. (German) Wiss. Z. Techn. Hochsch. Ilme-nau 11 (1965) 1-3. · Zbl 0132.20801
[15] M.A. de Freitas, V. Nikiforov, L. Patuzzi, Maxima of the Q -index: forbidden 4-cycle and 5-cycle, Electron. J. Linear Algebra 26 (2013), 905-916. · Zbl 1282.05166
[16] M.A. de Freitas, V. Nikiforov, L. Patuzzi, Maxima of the Q-index: graphs with no Ks,t, Linear Algebra Appl. 496 (2016), 381-391. · Zbl 1331.05150
[17] W. Haemers, G.R. Omidi, Universal adjacency matrices with two eigenvalues, Linear Algebra Appl. 435 (2011), 2520-2529. · Zbl 1221.05233
[18] B. He, Y.L. Jin, X.D. Zhang, Sharp bounds for the signless Laplacian spectral radius in terms of clique number, Linear Algebra Appl. 438 (2013), 3851-3861. · Zbl 1282.05119
[19] A.J. Hoffman, On eigenvalues and colorings of graphs, in Graph Theory and its Ap-plications, Academic Press, New York (1970), pp. 79-91. · Zbl 0221.05061
[20] R. Horn, C. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985, xiii+561 pp. · Zbl 0576.15001
[21] Y. Ikebe, T. Inagaki, S. Miyamoto, The monotonicity theorem, Cauchy’s interlace theorem, and the Courant-Fischer theorem, Amer. Math. Monthly 94 (1987), 352-354. · Zbl 0623.15010
[22] L.S. de Lima, C.S. Oliveira, N.M.M. de Abreu, V. Nikiforov, The smallest eigenvalue of the signless Laplacian, Linear Algebra Appl. 435 (2011), 2570-2584. · Zbl 1222.05180
[23] L.S. de Lima, V. Nikiforov, C.S. Oliveira, The clique number and the smallest Q-eigenvalue of graphs, Discrete Math. 339 (2016), 1744-1752. · Zbl 1333.05192
[24] L. Lovász, Combinatorial Problems and Exercises, North-Holland Publishing Co., Amsterdam-New York (1979), 551 pp. · Zbl 0439.05001
[25] R. Merris, A note on Laplacian graph eigenvalues, Linear Algebra Appl. 295 (1998), 33-35. · Zbl 0931.05053
[26] V. Nikiforov, Some new results in extremal graph theory, in Surveys in Combinatorics, Cambridge University Press (2011), pp. 141-181. · Zbl 1244.05125
[27] V. Nikiforov, Maxima of the Q-index: degenerate graphs, Electron. J. Linear Algebra 27 (2014), 250-257. · Zbl 1288.05164
[28] V. Nikiforov,O. Rojo, A note one the positive semidefinitness of Aα, Linear Algebra Appl 519 (2017), 156-163. · Zbl 1357.05090
[29] V. Nikiforov, X.Y. Yuan, Maxima of the Q-index: graphs without long paths, Electron. J. Linear Algebra 27 (2014), 504-514. · Zbl 1320.05078
[30] V. Nikiforov, X.Y. Yuan, Maxima of the Q-index: forbidden even cycles, Linear Algebra Appl. 471 (2015), 636-653. · Zbl 1307.05149
[31] W. So, Commutativity and spectra of Hermitian matrices, Linear Algebra Appl. 212-213 (1994), 121-129. · Zbl 0815.15005
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.