On graphs with the largest Laplacian index

Title:

On graphs with the largest Laplacian index

Creator:

Liu, Bolian, Chen, Zhibo, and Liu, Muhuo

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:248a9eb4-b9ae-4386-b654-bb42dfebfd39
uuid:248a9eb4-b9ae-4386-b654-bb42dfebfd39

Subject:

eigenvalue, Laplacian index, algebraic connectivity, semi-regular graph, regular graph, Hamiltonian graph, and planar graph

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

949-960

Source:

Czechoslovak Mathematical Journal | 2008 Volume:58 | Number:4

Harvested from:

CDK

Metadata only:

false