Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
Laplacian matrix; Laplacian spectral radius; girth; unicyclic graph
Laplacian matrix; Laplacian spectral radius; girth; unicyclic graph
Summary:
In this paper we consider the following problem: Over the class of all simple connected unicyclic graphs on $n$ vertices with girth $g$ ($n$, $g$ being fixed), which graph minimizes the Laplacian spectral radius? Let $U_{n,g}$ be the lollipop graph obtained by appending a pendent vertex of a path on $n-g$ $(n> g)$ vertices to a vertex of a cycle on $g\geq 3$ vertices. We prove that the graph $U_{n,g}$ uniquely minimizes the Laplacian spectral radius for $n\geq 2g-1$ when $g$ is even and for $n\geq 3g-1$ when $g$ is odd.
References:
[1] Fallat, S. M., Kirkland, S., Pati, S.: Minimizing algebraic connectivity over connected graphs with fixed girth. Discrete Math. 254 (2002), 115-142. DOI 10.1016/S0012-365X(01)00355-7 | MR 1909864 | Zbl 0995.05092
[2] Fallat, S. M., Kirkland, S., Pati, S.: Maximizing algebraic connectivity over unicyclic graphs. Linear Multilinear Algebra 51 (2003), 221-241. DOI 10.1080/0308108031000069182 | MR 1995656 | Zbl 1043.05074
[3] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. MR 0318007 | Zbl 0265.05119
[4] 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
[5] 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
[6] Guo, J.-M.: The effect on the Laplacian spectral radius of a graph by adding or grafting edges. Linear Algebra Appl. 413 (2006), 59-71. MR 2202092 | Zbl 1082.05059
[7] Guo, J.-M.: The Laplacian spectral radius of a graph under perturbation. Comput. Math. Appl. 54 (2007), 709-720. DOI 10.1016/j.camwa.2007.02.009 | MR 2347934 | Zbl 1155.05330
[8] Horn, R. A., Johnson, C. R.: Matrix Analysis. Reprinted with corrections Cambridge University Press, Cambridge (1990). MR 1084815 | Zbl 0704.15002
[9] Lal, A. K., Patra, K. L.: Maximizing Laplacian spectral radius over trees with fixed diameter. Linear Multilinear Algebra 55 (2007), 457-461. DOI 10.1080/03081080600618738 | MR 2363546 | Zbl 1124.05064
[10] Merris, R.: Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197-198 (1994), 143-176. MR 1275613 | Zbl 0802.05053
[11] Merris, R.: A survey of graph Laplacians. Linear Multilinear Algebra 39 (1995), 19-31. DOI 10.1080/03081089508818377 | MR 1374468 | Zbl 0832.05081
[12] Mohar, B.: The Laplacian spectrum of graphs. Alavi, Y. Graph Theory, Combinatorics and Applications, Kalamazoo, MI, 1988, Vol. 2 Wiley-Intersci. Publ. Wiley, New York 871-898 (1991). MR 1170831 | Zbl 0840.05059
Search
Partner of
