Colin de Verdière graph invariant
From Wikipedia, the free encyclopedia
Colin de Verdière's invariant is a graph parameter μ(G) for any graph G which has been introduced by Colin de Verdière in 1990, motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.
Let G = (V,E) be a loopless simple graph. Assume without loss of generality that 
. Then μ(G) is the largest corank of any matrix 
such that:
- (M1) for all i,j with
: Mi,j < 0 if i and j are adjacent, and Mi,j = 0 if i and j are nonadjacent; - (M2) M has exactly one negative eigenvalue, of multiplicity 1;
- (M3) there is no nonzero matrix
such that MX = 0 and such that Xi,j = 0 whenever i = j or 
.
This graph parameter is minor monotone:
- If H is a minor of G then
.
This parameter allows an algebraic characterization of some topological properties:
if and only if G is a disjoint union of paths;
if and only if G is outerplanar;
if and only if G is planar;
if and only if G is linklessly embeddable.
[edit] References
- Y. Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, Journal of Combinatorial Theory, Series B 50 (1990) 11-21.
- Y. Colin de Verdière, On a new graph invariant and a criterion for planarity, in: Graph Structure Theory (N. Robertson, P. Seymour, eds.), Contemporary Mathematics, American Mathematical Society, Providence, Rhode Island, 1993, pp. 137-147.
- L. Lovász and A. Schrijver, A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs. Proc. Amer. Math. Soc., 126(5):1275-1285, 1998.
- N. Robertson, P. Seymour, R. Thomas, Sachs' linkless embedding conjecture, Journal of Combinatorial Theory, Series B 64 (1995) 185-227.
.svg){kind=small}
