Home » Subject » Graph Theory » Algebraic G.T.
Importance: Medium ✭✭
Author(s): Guo, Ji-Ming
Subject: Graph Theory
» Algebraic Graph Theory
Keywords: degree sequence
Laplacian matrix
Recomm. for undergrads: no
Posted by: Robert Samal
on: June 22nd, 2007
Conjecture   If $ G $ is a connected graph on $ n $ vertices, then $ c_k(G) \ge d_k(G) $ for $ k = 1, 2, \dots, n-1 $.

(Reproduced from [M].)

Let $ L = D - A $ be the Laplacian matrix of a graph $ G $ of order $ n $. Let $ t_k $ be the $ k $-th largest eigenvalue of $ L $ ($ k = 1,\dots,n $). For the purpose of this problem, we call the number $$ c_k = c_k(G) = t_k + k - 2 $$ the $ k $-th Laplacian degree of $ G $. In addition to that, let $ d_k(G) $ be the $ k $-th largest (usual) degree in $ G $. It is known that every connected graph satisfies $ c_k(G) \ge d_k(G) $ for $ k = 1 $ [GM], $ k = 2 $ [LP] and for $ k = 3 $ [G].

Bibliography

[GM] R. Grone, R. Merris, The Laplacian spectrum of a graph II, SIAM J. Discrete Math.7 (1994) 221-229. MathSciNet

[LP] J.S. Li, Y.L. Pan, A note on the second largest eigenvalue of the Laplacian matrix of a graph, Linear Multilin. Algebra 48 (2000) 117-121. MathSciNet

*[G] J.-M. Guo, On the third largest Laplacian eigenvalue of a graph, Linear Multilin. Algebra 55 (2007) 93-102. MathSciNet

[M] B. Mohar, Problem of the Month


* indicates original appearance(s) of problem.
2 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options