Previous |  Up |  Next

Article

Keywords:
Laplacian eigenvalues; spread
Summary:
The Laplacian spread of a graph is defined as the difference between the largest and second smallest eigenvalues of the Laplacian matrix of the graph. In this paper, bounds are obtained for the Laplacian spread of graphs. By the Laplacian spread, several upper bounds of the Nordhaus-Gaddum type of Laplacian eigenvalues are improved. Some operations on Laplacian spread are presented. Connected $c$-cyclic graphs with $n$ vertices and Laplacian spread $n-1$ are discussed.
References:
[1] Bao, Y. H., Tan, Y. Y., Fan, Y. Z.: The Laplacian spread of unicyclic graphs. Appl. Math. Lett. 22 (2009), 1011-1015. DOI 10.1016/j.aml.2009.01.023 | MR 2522991 | Zbl 1179.05069
[2] Chen, Y., Wang, L.: The Laplacian spread of tricyclic graphs. Electron. J. Comb. 16 (2009), R80. MR 2529789 | Zbl 1230.05198
[3] Cvetković, D. M., Doob, M., Sachs, H.: Spectra of Graphs. VEB Deutscher Verlag der Wissenschaften Berlin (1980). Zbl 0458.05042
[4] Das, K. C.: The Laplacian spectrum of a graph. Comput. Math. Appl. 48 (2004), 715-724. DOI 10.1016/j.camwa.2004.05.005 | MR 2105246 | Zbl 1058.05048
[5] Dam, E. R. van, Haemers, W. H.: Graphs with constant $\mu$ and $\overline{\mu}$. Discrete Math. 182 (1998), 293-307. DOI 10.1016/S0012-365X(97)00150-7 | MR 1603715
[6] Fan, Y. Z., Xu, J., Wang, Y., Liang, D.: The Laplacian spread of a tree. Discrete Math. Theor. Comput. Sci. 10 (2008), 79-86 Electronic only. MR 2383736 | Zbl 1153.05323
[7] Fan, Y., Li, S., Tan, Y.: The Laplacian spread of bicyclic graphs. J. Math. Res. Expo. 30 (2010), 17-28. MR 2605816
[8] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 98-305. MR 0318007 | Zbl 0265.05119
[9] Goldberg, F.: Bounding the gap between extremal Laplacian eigenvalues of graphs. Linear Algebra Appl. 416 (2006), 68-74. DOI 10.1016/j.laa.2005.07.007 | MR 2232920 | Zbl 1107.05059
[10] Gregory, D. A., Hershkowitz, D., Kirkland, S. J.: The spread of the spectrum of a graph. Linear Algebra Appl. 332-334 (2001), 23-35. MR 1839425 | Zbl 0978.05049
[11] Grone, R., Merris, R., Sunder, V. S.: The Laplacian spectrum of a graph. SIAM J. Matrix Anal. Appl. 11 (1990), 218-239. DOI 10.1137/0611016 | MR 1041245 | Zbl 0733.05060
[12] Grone, R., Merris, R.: The Laplacian spectrum of a graph II. SIAM J. Discrete Math. 7 (1994), 221-229. DOI 10.1137/S0895480191222653 | MR 1271994 | Zbl 0795.05092
[13] Hong, Y., Shu, J. L.: A sharp upper bound for the spectral radius of the Nordhaus-Gaddum type. Discrete Math. 211 (2000), 229-232. DOI 10.1016/S0012-365X(99)90280-7 | MR 1735340 | Zbl 0952.05045
[14] Lazić, M.: On the Laplacian energy of a graph. Czech. Math. J. 56 (2006), 1207-1213. DOI 10.1007/s10587-006-0089-2 | MR 2280804 | Zbl 1164.05408
[15] Li, J., Shiu, W. C., Chan, W. H.: Some results on the Laplacian eigenvalues of unicyclic graphs. Linear Algebra Appl. 430 (2009), 2080-2093. MR 2503955 | Zbl 1225.05169
[16] Li, P., Shi, J. S., Li, R. L.: Laplacian spread of bicyclic graphs. J. East China Norm. Univ. (Nat. Sci. Ed.) 1 (2010), 6-9 Chinese. MR 2682387
[17] Liu, H., Lu, M., Tian, F.: On the Laplacian spectral radius of a graph. Linear Algebra Appl. 376 (2004), 135-141. MR 2014889 | Zbl 1032.05087
[18] Liu, B., Liu, M.-H.: On the spread of the spectrum of a graph. Discrete Math. 309 (2009), 2727-2732. DOI 10.1016/j.disc.2008.06.026 | MR 2523780 | Zbl 1194.05091
[19] Lu, M., Liu, H., Tian, F.: Laplacian spectral bounds for clique and independence numbers of graphs. J. Comb. Theory, Ser. B 97 (2007), 726-732. DOI 10.1016/j.jctb.2006.12.003 | MR 2344135 | Zbl 1122.05072
[20] Merris, R.: Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197-198 (1994), 143-176. MR 1275613 | Zbl 0802.05053
[21] Nordhaus, E. A., Gaddum, J. W.: On complementary graphs. Am. Math. Mon. 63 (1956), 175-177. DOI 10.2307/2306658 | MR 0078685 | Zbl 0070.18503
[22] Ozeki, N.: On the estimation of the inequality by the maximum. J. College Arts Chiba Univ. 5 (1968), 199-203. MR 0254198
[23] Shi, L.: Bounds on the (Laplacian) spectral radius of graphs. Linear Algebra Appl. 422 (2007), 755-770. DOI 10.1016/j.laa.2006.12.003 | MR 2305155 | Zbl 1113.05065
[24] You, Z., Liu, B.: The minimum Laplacian spread of unicyclic graphs. Linear Algebra Appl. 432 (2010), 499-504. DOI 10.1016/j.laa.2009.08.027 | MR 2577695 | Zbl 1206.05066
[25] Zhang, X.: On the two conjectures of Graffiti. Linear Algebra Appl. 385 (2004), 369-379. MR 2063360 | Zbl 1051.05062
[26] Zhou, B.: On sum of powers of the Laplacian eigenvalues of graphs. Linear Algebra Appl. 429 (2008), 2239-2246. DOI 10.1016/j.laa.2008.06.023 | MR 2446656 | Zbl 1144.05325
Partner of
EuDML logo