Open Problem Garden

Importance: Medium ✭✭

Author(s):

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

Open Problem Garden

Bibliography

Reply

Navigate

Recent Activity