Previous |  Up |  Next

Article

Keywords:
unicyclic graph; Laplacian eigenvalue; multiplicity; bound
Summary:
Let $G$ be a connected graph of order $n$ and $U$ a unicyclic graph with the same order. We firstly give a sharp bound for $m_{G}(\mu )$, the multiplicity of a Laplacian eigenvalue $\mu $ of $G$. As a straightforward result, $m_{U}(1)\le n-2$. We then provide two graph operations (i.e., grafting and shifting) on graph $G$ for which the value of $m_{G}(1)$ is nondecreasing. As applications, we get the distribution of $m_{U}(1)$ for unicyclic graphs on $n$ vertices. Moreover, for the two largest possible values of $m_{U}(1)\in \{n-5,n-3\}$, the corresponding graphs $U$ are completely determined.
References:
[1] Akbari, S., Kiani, D., Mirzakhah, M.: The multiplicity of Laplacian eigenvalue two in unicyclic graphs. Linear Algebra Appl. 445 (2014), 18-28. DOI 10.1016/j.laa.2013.11.022 | MR 3151261 | Zbl 1292.05164
[2] Akbari, S., Dam, E. R. van, Fakharan, M. H.: Trees with a large Laplacian eigenvalue multiplicity. Linear Algebra Appl. 586 (2020), 262-273. DOI 10.1016/j.laa.2019.10.011 | MR 4027756 | Zbl 1429.05118
[3] Andrade, E., Cardoso, D. M., Pastén, G., Rojo, O.: On the Faria's inequality for the Laplacian and signless Laplacian spectra: A unified approach. Linear Algebra Appl. 472 (2015), 81-86. DOI 10.1016/j.laa.2015.01.026 | MR 3314367 | Zbl 1307.05136
[4] Barik, S., Lal, A. K., Pati, S.: On trees with Laplacian eigenvalue one. Linear Multilinear Algebra 56 (2008), 597-610. DOI 10.1080/03081080600679029 | MR 2457687 | Zbl 1149.05029
[5] Brouwer, A. E., Haemers, W. H.: Spectra of Graphs. Universitext. Springer, New York (2012). DOI 10.1007/978-1-4614-1939-6 | MR 2882891 | Zbl 1231.05001
[6] Cvetković, D. M., Rowlinson, P., Simić, S.: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts 75. Cambridge University Press, Cambridge (2010). DOI 10.1017/CBO9780511801518 | MR 2571608 | Zbl 1211.05002
[7] Das, K. C.: Sharp lower bounds on the Laplacian eigenvalues of trees. Linear Algebra Appl. 384 (2004), 155-169. DOI 10.1016/j.laa.2004.01.012 | MR 2055349 | Zbl 1047.05027
[8] Doob, M.: Graphs with a small number of distinct eigenvalues. Ann. N. Y. Acad. Sci. 175 (1970), 104-110. DOI 10.1111/j.1749-6632.1970.tb56460.x | MR 0263674 | Zbl 0241.05112
[9] Faria, I.: Permanental roots and the star degree of a graph. Linear Algebra Appl. 64 (1985), 255-265. DOI 10.1016/0024-3795(85)90281-2 | MR 0776531 | Zbl 0559.05041
[10] Grone, R., Merris, R.: Algebraic connectivity of trees. Czech. Math. J. 37 (1987), 660-670. DOI 10.21136/CMJ.1987.102192 | MR 0913997 | Zbl 0681.05022
[11] Grone, R., Merris, R., Sunder, V. S.: The Laplacian spectrum of a graph. SIAM J. Matrix Anal. Appl. 11 (1990), 218-238. DOI 10.1137/0611016 | MR 1041245 | Zbl 0733.05060
[12] Guo, J.-M., Feng, L., Zhang, J.-M.: On the multiplicity of Laplacian eigenvalues of graphs. Czech. Math. J. 60 (2010), 689-698. DOI 10.1007/s10587-010-0063-x | MR 2672410 | Zbl 1224.05297
[13] Huang, X., Huang, Q.: On regular graphs with four distinct eigenvalues. Linear Algebra Appl. 512 (2017), 219-233. DOI 10.1016/j.laa.2016.09.043 | MR 3567523 | Zbl 1348.05125
[14] Kirkland, S.: A bound on algebra connectivity of a graph in terms of the number cutpoints. Linear Multilinear Algebra 47 (2000), 93-103. DOI 10.1080/03081080008818634 | MR 1752168 | Zbl 0947.05052
[15] Lu, L., Huang, Q., Huang, X.: On graphs with distance Laplacian spectral radius of multiplicity $n-3$. Linear Algebra Appl. 530 (2017), 485-499. DOI 10.1016/j.laa.2017.05.044 | MR 3672973 | Zbl 1367.05134
[16] Rowlinson, P.: On graphs with just three distinct eigenvalues. Linear Algebra Appl. 507 (2016), 462-473. DOI 10.1016/j.laa.2016.06.031 | MR 3536969 | Zbl 1343.05096
[17] Dam, E. R. van: Nonregular graphs with three eigenvalues. J. Comb. Theory, Ser. B 73 (1998), 101-118. DOI 10.1006/jctb.1998.1815 | MR 1631983 | Zbl 0917.05044
[18] Dam, E. R. van, Koolen, J. H., Xia, Z.-J.: Graphs with many valencies and few eigenvalues. Electron. J. Linear Algebra 28 (2015), 12-24. DOI 10.13001/1081-3810.2987 | MR 3386384 | Zbl 1320.05082
Partner of
EuDML logo