Geodesic
On graphs with the largest Laplacian index
Czechoslovak Mathematical Journal, Tome 58 (2008) no. 4, pp. 949-960 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C50, 15A36, 15A42
Keywords: eigenvalue; Laplacian index; algebraic connectivity; semi-regular graph; regular graph; Hamiltonian graph; planar graph 
@article{CMJ_2008_58_4_a6,
     author = {Liu, BoLian and Chen, Zhibo and Liu, Muhuo},
     title = {On graphs with the largest {Laplacian} index},
     journal = {Czechoslovak Mathematical Journal},
     pages = {949--960},
     year = {2008},
     volume = {58},
     number = {4},
     mrnumber = {2471159},
     zbl = {1174.05078},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a6/}
}
TY  - JOUR
AU  - Liu, BoLian
AU  - Chen, Zhibo
AU  - Liu, Muhuo
TI  - On graphs with the largest Laplacian index
JO  - Czechoslovak Mathematical Journal
PY  - 2008
SP  - 949
EP  - 960
VL  - 58
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a6/
LA  - en
ID  - CMJ_2008_58_4_a6
ER  - 
%0 Journal Article
%A Liu, BoLian
%A Chen, Zhibo
%A Liu, Muhuo
%T On graphs with the largest Laplacian index
%J Czechoslovak Mathematical Journal
%D 2008
%P 949-960
%V 58
%N 4
%U http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a6/
%G en
%F CMJ_2008_58_4_a6
Liu, BoLian; Chen, Zhibo; Liu, Muhuo. On graphs with the largest Laplacian index. Czechoslovak Mathematical Journal, Tome 58 (2008) no. 4, pp. 949-960. http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a6/

[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 | Zbl

[4] Gracssi, R.: Relevant inequalities in graph connectivity. Arch. Ineqal. Appl. 2 (2004), 183-198. | MR

[5] Gutman, I.: The star is the tree with greatest Laplacian eignvalue. Kragujevac J. Math. 24 (2002), 61-65. | MR

[6] Haemers, W. H.: Interlacing eigenvalues and graphs. Linear Algebra Appl. 227-228 (1995), 593-616. | MR | Zbl

[7] Harary, F.: Graph Theory. Addison-Wesley Reading (1969). | MR | Zbl

[8] Merris, R.: Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197-198 (1994), 143-176. | MR | Zbl