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{C}_{k} and a path Pn{P}_{n}. Using two different approaches, we show that their Laplacian index converges to Δ2Δ−1=92\frac{{\Delta }^{2}}{\Delta -1}=\frac{9}{2} as n,k→∞n,k\to \infty , where Δ=3\Delta =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.

Keywords

• laplacian matrix
• tadpole graph
• rational difference equation
• 05c50
• 15a18
• 15b57