eigenvalue; Laplacian index; algebraic connectivity; semi-regular graph; regular graph; Hamiltonian graph; planar graph
Let $G$ be a connected simple graph on $n$ vertices. The Laplacian index of $G$, namely, the greatest Laplacian eigenvalue of $G$, is well known to be bounded above by $n$. In this paper, we give structural characterizations for graphs $G$ with the largest Laplacian index $n$. Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on $n$ and $k$ for the existence of a $k$-regular graph $G$ of order $n$ with the largest Laplacian index $n$. We prove that for a graph $G$ of order $n \geq 3$ with the largest Laplacian index $n$, $G$ is Hamiltonian if $G$ is regular or its maximum vertex degree is $\triangle (G)=n/2$. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce miscellaneous related results.
 Bonday, J. A., Murty, U. S. R.: Graph Theory with Applications. Macmillan London (1976).
 Cvetkovic, D. M., Doob, M., Sachs, H.: Spectra of Graphs. Theory and Applications. VEB Deutscher Verlag der Wissenschaften Berlin (1980).
 Fiedler, M.: Algebraic connectivity of graphs
. Czechoslovak Math. J. 23 (1973), 298-305. MR 0318007
| Zbl 0265.05119
 Gracssi, R.: Relevant inequalities in graph connectivity
. Arch. Ineqal. Appl. 2 (2004), 183-198. MR 2106953
 Gutman, I.: The star is the tree with greatest Laplacian eignvalue
. Kragujevac J. Math. 24 (2002), 61-65. MR 1947659
 Haemers, W. H.: Interlacing eigenvalues and graphs
. Linear Algebra Appl. 227-228 (1995), 593-616. MR 1344588
| Zbl 0831.05044
 Merris, R.: Laplacian matrices of graphs: A survey
. Linear Algebra Appl. 197-198 (1994), 143-176. MR 1275613
| Zbl 0802.05053