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.
@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/
