# Article

Full entry | PDF   (0.2 MB)
Keywords:
eigenvalue; Laplacian index; algebraic connectivity; semi-regular graph; regular graph; Hamiltonian graph; planar graph
Summary:
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.
References:
[1] Bonday, J. A., Murty, U. S. R.: Graph Theory with Applications. Macmillan London (1976).
[2] Cvetkovic, D. M., Doob, M., Sachs, H.: Spectra of Graphs. Theory and Applications. VEB Deutscher Verlag der Wissenschaften Berlin (1980).
[3] Fiedler, M.: Algebraic connectivity of graphs. Czechoslovak Math. J. 23 (1973), 298-305. MR 0318007 | Zbl 0265.05119
[4] Gracssi, R.: Relevant inequalities in graph connectivity. Arch. Ineqal. Appl. 2 (2004), 183-198. MR 2106953
[5] Gutman, I.: The star is the tree with greatest Laplacian eignvalue. Kragujevac J. Math. 24 (2002), 61-65. MR 1947659
[6] Haemers, W. H.: Interlacing eigenvalues and graphs. Linear Algebra Appl. 227-228 (1995), 593-616. MR 1344588 | Zbl 0831.05044
[7] Harary, F.: Graph Theory. Addison-Wesley Reading (1969). MR 0256911 | Zbl 0196.27202
[8] Merris, R.: Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197-198 (1994), 143-176. MR 1275613 | Zbl 0802.05053

Partner of