TY - JOUR

T1 - On graphs with the largest Laplacian index

AU - Liu, Bolian

AU - Chen, Zhibo

AU - Liu, Muhuo

N1 - Funding Information:
The first author is supported by NNSF of China (No. 10771080) and SRFDP of China (No. 20070574006). The work was done when Z. Chen was on sabbatical in China.

PY - 2008/12

Y1 - 2008/12

N2 - 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 ≥ 3 with the largest Laplacian index n, G s Hamiltonian if G is regular or its maximum vertex degree is Δ(G) = n/2. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce miscellaneous related results.

AB - 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 ≥ 3 with the largest Laplacian index n, G s Hamiltonian if G is regular or its maximum vertex degree is Δ(G) = n/2. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce miscellaneous related results.

UR - http://www.scopus.com/inward/record.url?scp=58049171988&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58049171988&partnerID=8YFLogxK

U2 - 10.1007/s10587-008-0062-3

DO - 10.1007/s10587-008-0062-3

M3 - Article

AN - SCOPUS:58049171988

SN - 0011-4642

VL - 58

SP - 949

EP - 960

JO - Czechoslovak Mathematical Journal

JF - Czechoslovak Mathematical Journal

IS - 4

ER -