Home » Keyword index

eigenvalues


Graph Theory » Algebraic G.T.

The sum of the two largest eigenvalues ★★

Author(s): Gernert

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 $?

Keywords: eigenvalues; spectrum

Posted by mdevos
updated January 13th, 2009
4 comments
Graph Theory » Coloring » Vertex coloring

Alon-Saks-Seymour Conjecture ★★★

Author(s): Alon; Saks; Seymour

Conjecture   If $ G $ is a simple graph which can be written as an union of $ m $ edge-disjoint complete bipartite graphs, then $ \chi(G) \le m+1 $.

Keywords: coloring; complete bipartite graph; eigenvalues; interlacing

Posted by mdevos
updated February 26th, 2010
1 comment
Graph Theory » Algebraic G.T.

Fowler's Conjecture on eigenvalues of (3,6)-polyhedra ★★

Author(s): Fowler

Conjecture   Let $ G $ be the graph of a $ (3,6) $-polyhedron with $ 2k + 4 $ vertices. Then the eigenvalues of $ G $ can be partitioned into three classes: $ K = \{3, -1, -1, -1\} $, $ P = {x_1, ..., x_k\} $ (where $ x_i $ is nonnegative for $ i = 1, \dots , k $), and $ N = - P $.

Keywords: (3,6)-polyhedron; eigenvalues

Posted by Robert Samal
updated April 8th, 2008
4 comments
Syndicate content