On the Laplacian index of tadpole graphs

Abstract

In this article, we study the Laplacian index of tadpole graphs, which are unicyclic graphs formed by adding an edge between a cycle Ck and a path Pn. Using two different approaches, we show that their Laplacian index converges to = − Δ Δ 1 9 2 2 as n, k → ∞, where Δ = 3 is the maximum degree of the graph. This limit is known as the Hoffman’s limit for the Laplacian matrix. The first technique is a linear time algorithm presented in [R. Braga, V. Rodrigues, and R. Silva, Locating eigenvalues of a symmetric matrix whose graph is unicyclic, Trends in Comput. Appl. Math. 22 (2021), no. 4, 659–674] that diagonalizes the matrix preserving its inertia. Here, we adapt this algorithm to the Laplacian index of a tadpole graph. The second method is to apply a formula presented in [V. Trevisan and E. R. Oliveira, Applications of rational difference equations to spectra graph theory, J. Difference Equ. Appl. 27 (2021), 1024–1051] for solving rational difference equations that appear when applying the diagonalization algorithm in some cases.