članak: 1 od 1  
Publications de l'Institut Mathematique
2009, vol. 85, br. 99, str. 19-33
jezik rada: engleski
članak
doi:10.2298/PIM0999019C

Towards a spectral theory of graphs based on the signless Laplacian, I
(naslov ne postoji na srpskom)
Srpska akademija nauke i umetnosti (SANU), Beograd, Matematički institut

e-adresa: ecvetkod@etf.bg.ac.rs, sksimic@mi.sanu.ac.rs

Projekat Ministarstva nauke Republike Srbije, br. 144015G

Sažetak

(ne postoji na srpskom)
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-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.

Ključne reči

Reference

Cao, D. (1995) The distribution of eigenvalues of graphs. Linear Algebra and its Applications, 216: 211
Cardoso, D.M., Cvetkovic, D.M., Rowlinson, P., Simic, S.K. (2008) A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph
Chung, F.R.K. (1997) Spectral graph theory. u: CBMS Regional Conference Series in Mathematics, Providence, RI: American Mathematical Society / AMS
Cvetković, D. (2005) Signless Laplacians and line graphs. Bulletin: Classe des sciences mathématiques et natturalles - Sciences mathématiques, vol. 131, br. 30, str. 85-92
Cvetković, D., Rowlinson, P., Simić, S.K. (2007) Eigenvalue bounds for the signless laplacian. Publications de l'Institut Mathematique, vol. 81, br. 95, str. 11-27
Cvetković, D., Rowlinson, Peter., Simić, S.K. (2007) Signless Laplacians of finite graphs
Cvetković, D.M. (2008) New theorems for signless Laplacian eigenvalues. Bulletin: Classe des sciences mathématiques et natturalles - Sciences mathématiques, vol. 137, br. 33, str. 131-146
Cvetković, D.M., Doob, M., Sachs, H. (1995) Spectra of graphs: Theory and application. Heidelberg-Leipzig: Barth Verlag
Cvetković, D.M., Rowlinson, P., Simić, S.K. (1997) Eigenspaces of graphs. u: Encyclopedia of Mathematics and its Applications, Cambridge, itd: Cambridge University Press / CUP, vol. 66
Cvetković, D.M., Rowlinson, P., Simić, S.K. (2004) Spectral generalizations of line graphs: On graphs with least eigenvalue -2. Cambridge, itd: Cambridge University Press / CUP
Daneshgar, A., Hajiabolhassan, H. (2006) Graph homomorphisms and nodal domains. Linear Algebra Appl, 418, 44-52
Dedo, E. (1981) La ricostruibilita del polinomio caratteristico del commutato di un grafo. Boll. Unione Mat. Ital, 18A(5), 423-429
Fan, Y.Z., Tam, B.S., Zhou, J. (2008) Maximizing spectral radius of unoriented Laplacian matrix over bicyclic graphs of a given order. Linear and Multilinear Algebra, 56(4): 381
Feng, L., Li, Q., Zhang, X.D. (2007) Minimizing the Laplacian spectral radius of trees with given matching number. Linear and Multilinear Algebra, 55(2): 199
Feng, L., Yu, G. (2007) No star-like trees are Laplacian co-spectral. Applicable Analysis and Discrete Mathematics, br. 18, str. 46-51
Haemers, W., Spence, E. (2004) Enumeration of cospectral graphs. European J. Combin., 25, 2, 199-211
Hoffman, A.J., Smith, J.H. (1975) On the spectral radii of topologically equivalent graphs. u: Fiedler M. (ur.) Recent advances in graph theory, Praha: Academia, 273-281
Hong, Y. (1988) A bound on the spectral radius of graphs. Linear Algebra Appl, 108, pp. 135-139
Lepović, M. (2003) Some results on starlike trees and sunlike graphs. Journal of Applied Mathematics and Computing, 11(1-2): 109
Lepović, M.V., Gutman, I. (2002) No starlike trees are cospectral
Li, Q., Feng, K. (1979) On the largest eigenvalue of a graph. Acta Math. Sinica, 2, 2, 167-175
Marino, M.C., Sciriha, I., Simić, S.K., Tošić, D.V. (2006) More about singular line graphs of trees. Publications de l'Institut Mathematique, vol. 79, br. 93, str. 1-12
Oliveira, C.S., de Lima, L.S., de Abreu, N.M.M., Hansen, P. (2007) Bounds on the index of the signless Laplacian of a graph. Les Cahiers du GERAD, G-72
Simić, S.K. (1987) Some results on the largest eigenvalue of a graph. Ars Comb, 24A, 211-219
Simić, S.K., Stanić, Z. (2007) Q-integral graphs with edge-degrees at most five. Discrete Mathematics
Simić, S.K., Stanić, Z. (2007) The polynomial reconstruction is unique for the graphs whose deck-spectra are bounded from below by −2. Linear Algebra Appl, 55(1), 35-43
Simić, S.K., Stanić, Z. (to appear) On some forests determined by their Laplacian (signless Laplacian) spectrum
Stanić, Z. (2007) Some reconstructions in spectral graph theory and Q-integral graphs. Belgrade: Faculty of Mathematics, Doctoral Thesis
Stanić, Z. (2007) There are exactly 172 connected Q-integral graphs up to 10 vertices1. Journal of Mathematics, Novi Sad, vol. 37, br. 2, str. 193-205
Stevanović, D. (2007) Research problems from the Aveiro Workshop on Graph Spectra
Tam, B.S., Fan, Y.Z., Zhou, J. (2008) Unoriented Laplacian maximizing graphs are degree maximal. Linear Algebra and its Applications, 429(4): 735
Tutte, W.T. (1979) All the king's horses: A guide to reconstruction. u: Bondy J.A., Murty U.S.R. (ur.) Graph theory and Related Topics, Proc. Conf. University of Waterloo, Waterloo, Ont. 1977, New York: Academic Press, str. 15-33
van Dam, E.R., Haemers, W. (2003) Which graphs are determined by their spectrum?. Linear Algebra Appl, 373, 241-272
Zhou, B., Gutman, I. (2008) A connection between ordinary and Laplacian spectra of bipartite graphs. Linear and Multilinear Algebra, 56(3): 305
Zhu, P., Wilson, R.C. (2005) A study of graph spectra for comparing graphs. u: British Machine Vision Conference, 5-8 September, Oxford Brookes University, BMVA, 679-688