×
Das, Kinkar Ch.

On conjectures involving second largest signless Laplacian eigenvalue of graphs. (English) Zbl 1195.05040

Linear Algebra Appl. 432, No. 11, 3018-3029 (2010).
Summary: Let \(G=(V,E)\) be a simple graph. Denote by \(D(G)\) the diagonal matrix of its vertex degrees and by \(A(G)\) its adjacency matrix. Then the Laplacian matrix of \(G\) is \(L(G)=D(G)-A(G)\) and the signless Laplacian matrix of \(G\) is \(Q(G)=D(G)+A(G)\). In this paper we obtain a lower bound on the second largest signless Laplacian eigenvalue and an upper bound on the smallest signless Laplacian eigenvalue of \(G\). In [5], Cvetković et al. have given a series of 30 conjectures on Laplacian eigenvalues and signless Laplacian eigenvalues of \(G\) (see also [1]). Here we prove five conjectures.

Cited in 65 Documents

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C35 Extremal problems in graph theory

Keywords:

graph; Laplacian matrix; algebraic connectivity; signless Laplacian matrix; the largest signless Laplacian eigenvalue; the second largest signless Laplacian eigenvalue; smallest signless Laplacian eigenvalue
PDF BibTeX XML Cite
\textit{K. Ch. Das}, Linear Algebra Appl. 432, No. 11, 3018--3029 (2010; Zbl 1195.05040)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] M. Aouchiche, P. Hansen, A survey of automated conjectures in spectral graph theory, Linear Algebra Appl., in press, doi:10.1016/j.laa.2009.06.015. · Zbl 1218.05087
[2] Cardoso, D.M.; Cvetković, D.; Rowlinson, P.; Simić, S.K., A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph, Linear algebra appl., 429, 2770-2780, (2008) · Zbl 1148.05046
[3] Cvetković, D.; Doob, M.; Sachs, H., Spectra of graphs, (1995), Barth Heidelberg · Zbl 0824.05046
[4] Cvetković, D.; Rowlinson, P.; Simić, S.K., Signless Laplacians of finite graphs, Linear algebra appl., 423, 155-171, (2007) · Zbl 1113.05061
[5] Cvetković, D.; Rowlinson, P.; Simić, S.K., Eigenvalue bounds for the signless Laplacian, Publ. inst. math. (beogr.) (N.S.), 81, 95, 11-27, (2007) · Zbl 1164.05038
[6] Cvetković, D.; Simić, S.K., Towards a spectral theory of graphs based on the signless Laplacian, I, Publ. inst. math. (beogr.) (N.S.), 85, 99, 19-33, (2009) · Zbl 1224.05293
[7] Das, K.C., An improved upper bound for Laplacian graph eigenvalues, Linear algebra appl., 368, 269-278, (2003) · Zbl 1020.05040
[8] Das, K.C., The Laplacian spectrum of a graph, Comput. math. appl., 48, 715-724, (2004) · Zbl 1058.05048
[9] Das, K.C., A characterization on graphs which achieve the upper bound for the largest Laplacian eigenvalue of graphs, Linear algebra appl., 376, 173-186, (2004) · Zbl 1042.05059
[10] Das, K.C., Sharp lower bounds on the Laplacian eigenvalues of trees, Linear algebra appl., 384, 155-169, (2004) · Zbl 1047.05027
[11] Das, K.C.; Lee, S.-G.; Cheon, G.-S., On the conjecture for certain Laplacian integral spectrum of graphs, J. graph theory, 63, 106-113, (2010) · Zbl 1209.05141
[12] Delorme, C.; Poljak, S., Combinatorial properties and the complexity of a MAX-cut approximation, Eur. J. combin., 14, 313-333, (1993) · Zbl 0780.05040
[13] Delorme, C.; Poljak, S., The performance of an eigenvalue bound on the MAX-cut problem in some classes of graphs, Discrete math., 111, 145-156, (1993) · Zbl 0786.05057
[14] Fallat, S.M.; Kirkland, S.J.; Molitierno, J.J.; Neumann, M., On graphs whose Laplacian matrices have distinct integer eigenvalues, J. graph theory, 50, 162-174, (2005) · Zbl 1077.05060
[15] -Z Fan, Y.; Tam, B.-S.; Zhou, J., Maximizing spectral radius of unoriented Laplacian matrix over bicyclic graphs of a given order, Linear and multilinear algebra, 56, 4, 381-397, (2008) · Zbl 1146.05032
[16] Fiedler, M., Algebraic connectivity of graphs, Czech. math. J., 37, 660-670, (1987) · Zbl 0681.05022
[17] Grone, R.; Merris, R., The Laplacian spectrum of a graph II^{∗}, SIAM J. discrete math., 7, 2, 221-229, (1994) · Zbl 0795.05092
[18] Gutman, I.; Gineityle, V.; Lepović, M.; Petrović, M., The high-energy band in the photoelectron spectrum of alkanes and its dependence on molecular structure, J. serb. chem. soc., 64, 673-680, (1999)
[19] Gutman, I.; Vidović, D.; Stevanović, D., Chemical applications of the Laplacian spectrum. VI. on the largest Laplacian eigenvalue of alkanes, J. serb. chem. soc., 67, 6, 407-413, (2002)
[20] Heuvel, J.V.D., Hamilton cycles and eigenvalues of graphs, Linear algebra appl., 226-228, 723-730, (1995) · Zbl 0846.05059
[21] Kirkland, S.J., Completion of Laplacian integral graphs via edge addition, Discrete math., 295, 75-90, (2005) · Zbl 1063.05094
[22] Li, J.-S.; Zhang, D., A new upper bound for eigenvalues of the Laplacian matrix of a graph, Linear algebra appl., 265, 93-100, (1997) · Zbl 0884.05062
[23] Li, J.-S.; Zhang, D., On Laplacian eigenvalues of a graph, Linear algebra appl., 285, 305-307, (1998) · Zbl 0931.05052
[24] Merris, R., Laplacian matrices of graphs: a survey, Linear algebra appl., 197, 198, 143-176, (1994) · Zbl 0802.05053
[25] Mohar, B., The Laplacian spectrum of graphs, Graph theory, combin. appl., 2, 871-898, (1991) · Zbl 0840.05059
[26] Oliveira, C.S.; Lima, L.S.; Abreu, N.M.M.; Kirkland, S., Bounds on the \(Q\)-spread of a graph, Linear algebra appl., 432, 2342-2351, (2010) · Zbl 1214.05082
[27] Pan, Y.-L., Sharp upper bounds for the Laplacian graph eigenvalues, Linear algebra appl., 355, 287-295, (2002) · Zbl 1015.05055
[28] Schott, J.R., Matrix analysis for statistics, (1997), John Wiley and Sons · Zbl 0872.15002
[29] Simić, S.K.; Stanić, Z., \(Q\)-integral graphs with edge-degrees at most five, Discrete math., 308, 4625-4634, (2008) · Zbl 1156.05037
[30] So, W., Rank one perturbation and its application to the Laplacian spectrum of a graph, Linear and multilinear algebra, 46, 193-198, (1999) · Zbl 0935.05065
[31] Solé, P., Expanding and forwarding, Discrete appl. math., 58, 67-78, (1995) · Zbl 0820.05034
[32] Stevanović, D., Research problems from the Aveiro workshop on graph spectra, Linear algebra appl., 423, 172-181, (2007) · Zbl 1290.05002
[33] Zhang, F., Matrix theory: basic results and techniques, (1999), Springer-Verlag New York · Zbl 0948.15001
[34] Zhang, X.-D., The signless Laplacian spectral radius of graphs with given degree sequences, Discrete appl. math., 157, 2928-2937, (2009) · Zbl 1213.05153
[35] Zhang, Y.; Liu, X.; Zhang, B.; Yong, X., The lollipop graph is determined by its \(Q\)-spectrum, Discrete math., 309, 3364-3369, (2009) · Zbl 1182.05084
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.