Home » Subject » Graph Theory » Algebraic G.T.
Importance: Medium ✭✭
Author(s): Gernert, Dieter
Subject: Graph Theory
» Algebraic Graph Theory
Keywords: eigenvalues
spectrum
Recomm. for undergrads: no
Posted by: mdevos
on: June 6th, 2007
Solved by: Vladimir Nikiforov, Linear Combinations of Graph Eigenvalues, Electronic Journal of Linear Algebra 15 pp 329-336
Problem   Let $ G $ be a graph on $ n $ vertices and let $ \lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n $ be the eigenvalues of $ G $. Is $ \lambda_1 + \lambda_2 \le n $?

This property does hold for all regular graphs $ G $. If $ G $ is $ k $-regular, then $ \lambda_1 = k $. Further, if we let $ \bar{G} $ denote the complement of $ G $ and let $ \bar{\lambda_1} \ge \bar{\lambda_2}, \ldots \ge \bar{\lambda_n} $ denote its eigenvalues, then $ \lambda_2 = -1 - \bar{\lambda_n} \le -1 + (n-k-1) $ (the second inequality here follows from the observation that $ \bar{G} $ is $ (n-k-1) $-regular).

Bibliography

Open Problems in Spectral Graph Theory (a list maintained by Dragan Stevanović).


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

Reply

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