Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth

Kamal Lochan Patra; Binod Kumar Sahoo

Czechoslovak Mathematical Journal (2013)

  • Volume: 63, Issue: 4, page 909-922
  • ISSN: 0011-4642

Abstract

top
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 ≥ 3 vertices. We prove that the graph U n , g uniquely minimizes the Laplacian spectral radius for n ≥ 2 g - 1 when g is even and for n ≥ 3 g - 1 when g is odd.

How to cite

top

Patra, Kamal Lochan, and Sahoo, Binod Kumar. "Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth." Czechoslovak Mathematical Journal 63.4 (2013): 909-922. <http://eudml.org/doc/260824>.

@article{Patra2013,
abstract = {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\ge 3$ vertices. We prove that the graph $U_\{n,g\}$ uniquely minimizes the Laplacian spectral radius for $n\ge 2g-1$ when $g$ is even and for $n\ge 3g-1$ when $g$ is odd.},
author = {Patra, Kamal Lochan, Sahoo, Binod Kumar},
journal = {Czechoslovak Mathematical Journal},
keywords = {Laplacian matrix; Laplacian spectral radius; girth; unicyclic graph; Laplacian matrix; Laplacian spectral radius; girth; unicyclic graph},
language = {eng},
number = {4},
pages = {909-922},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth},
url = {http://eudml.org/doc/260824},
volume = {63},
year = {2013},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 63
IS - 4
SP - 909
EP - 922
AB - 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\ge 3$ vertices. We prove that the graph $U_{n,g}$ uniquely minimizes the Laplacian spectral radius for $n\ge 2g-1$ when $g$ is even and for $n\ge 3g-1$ when $g$ is odd.
LA - eng
KW - Laplacian matrix; Laplacian spectral radius; girth; unicyclic graph; Laplacian matrix; Laplacian spectral radius; girth; unicyclic graph
UR - http://eudml.org/doc/260824
ER -

References

top
  1. Fallat, S. M., Kirkland, S., Pati, S., 10.1016/S0012-365X(01)00355-7, Discrete Math. 254 (2002), 115-142. (2002) Zbl0995.05092MR1909864DOI10.1016/S0012-365X(01)00355-7
  2. Fallat, S. M., Kirkland, S., Pati, S., 10.1080/0308108031000069182, Linear Multilinear Algebra 51 (2003), 221-241. (2003) Zbl1043.05074MR1995656DOI10.1080/0308108031000069182
  3. Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), 298-305. (1973) Zbl0265.05119MR0318007
  4. Grone, R., Merris, R., 10.1137/S0895480191222653, SIAM J. Discrete Math. 7 (1994), 221-229. (1994) Zbl0795.05092MR1271994DOI10.1137/S0895480191222653
  5. Grone, R., Merris, R., Sunder, V. S., 10.1137/0611016, SIAM J. Matrix Anal. Appl. 11 (1990), 218-238. (1990) Zbl0733.05060MR1041245DOI10.1137/0611016
  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. (2006) Zbl1082.05059MR2202092
  7. Guo, J.-M., 10.1016/j.camwa.2007.02.009, Comput. Math. Appl. 54 (2007), 709-720. (2007) Zbl1155.05330MR2347934DOI10.1016/j.camwa.2007.02.009
  8. Horn, R. A., Johnson, C. R., Matrix Analysis, Reprinted with corrections Cambridge University Press, Cambridge (1990). (1990) Zbl0704.15002MR1084815
  9. Lal, A. K., Patra, K. L., 10.1080/03081080600618738, Linear Multilinear Algebra 55 (2007), 457-461. (2007) Zbl1124.05064MR2363546DOI10.1080/03081080600618738
  10. Merris, R., Laplacian matrices of graphs: A survey, Linear Algebra Appl. 197-198 (1994), 143-176. (1994) Zbl0802.05053MR1275613
  11. Merris, R., 10.1080/03081089508818377, Linear Multilinear Algebra 39 (1995), 19-31. (1995) Zbl0832.05081MR1374468DOI10.1080/03081089508818377
  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). (1991) Zbl0840.05059MR1170831

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.