Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
eigenvalue; Laplacian index; algebraic connectivity; semi-regular graph; regular graph; Hamiltonian graph; planar graph
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
Search
Partner of
