Geodesic
Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth
Czechoslovak Mathematical Journal, Tome 63 (2013) no. 4, pp. 909-922
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-013-0061-x
Classification : 05C50
Keywords: Laplacian matrix; Laplacian spectral radius; girth; unicyclic graph 
@article{10_1007_s10587_013_0061_x,
     author = {Patra, Kamal Lochan and Sahoo, Binod Kumar},
     title = {Minimizing {Laplacian} spectral radius of unicyclic graphs with fixed girth},
     journal = {Czechoslovak Mathematical Journal},
     pages = {909--922},
     year = {2013},
     volume = {63},
     number = {4},
     doi = {10.1007/s10587-013-0061-x},
     mrnumber = {3165504},
     zbl = {06373951},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0061-x/}
}
TY  - JOUR
AU  - Patra, Kamal Lochan
AU  - Sahoo, Binod Kumar
TI  - Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth
JO  - Czechoslovak Mathematical Journal
PY  - 2013
SP  - 909
EP  - 922
VL  - 63
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0061-x/
DO  - 10.1007/s10587-013-0061-x
LA  - en
ID  - 10_1007_s10587_013_0061_x
ER  - 
%0 Journal Article
%A Patra, Kamal Lochan
%A Sahoo, Binod Kumar
%T Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth
%J Czechoslovak Mathematical Journal
%D 2013
%P 909-922
%V 63
%N 4
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0061-x/
%R 10.1007/s10587-013-0061-x
%G en
%F 10_1007_s10587_013_0061_x
Patra, Kamal Lochan; Sahoo, Binod Kumar. Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth. Czechoslovak Mathematical Journal, Tome 63 (2013) no. 4, pp. 909-922. doi: 10.1007/s10587-013-0061-x

[1] Fallat, S. M., Kirkland, S., Pati, S.: Minimizing algebraic connectivity over connected graphs with fixed girth. Discrete Math. 254 (2002), 115-142. | DOI | MR | Zbl

[2] Fallat, S. M., Kirkland, S., Pati, S.: Maximizing algebraic connectivity over unicyclic graphs. Linear Multilinear Algebra 51 (2003), 221-241. | DOI | MR | Zbl

[3] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. | MR | Zbl

[4] Grone, R., Merris, R.: The Laplacian spectrum of a graph. II. SIAM J. Discrete Math. 7 (1994), 221-229. | DOI | MR | Zbl

[5] Grone, R., Merris, R., Sunder, V. S.: The Laplacian spectrum of a graph. SIAM J. Matrix Anal. Appl. 11 (1990), 218-238. | DOI | MR | Zbl

[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 | Zbl

[7] Guo, J.-M.: The Laplacian spectral radius of a graph under perturbation. Comput. Math. Appl. 54 (2007), 709-720. | DOI | MR | Zbl

[8] Horn, R. A., Johnson, C. R.: Matrix Analysis. Reprinted with corrections Cambridge University Press, Cambridge (1990). | MR | Zbl

[9] Lal, A. K., Patra, K. L.: Maximizing Laplacian spectral radius over trees with fixed diameter. Linear Multilinear Algebra 55 (2007), 457-461. | DOI | MR | Zbl

[10] Merris, R.: Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197-198 (1994), 143-176. | MR | Zbl

[11] Merris, R.: A survey of graph Laplacians. Linear Multilinear Algebra 39 (1995), 19-31. | DOI | MR | Zbl

[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 | Zbl

Cité par Sources :