Colin de Verdière graph invariant

From Wikipedia, the free encyclopedia

You have new messages (last change).

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 V=\{1,\dots,n\}. Then μ(G) is the largest corank of any matrix M=(M_{i,j})\in\mathbb{R}^{(n)} such that:

  • (M1) for all i,j with i\neq j: 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 X=(X_{i,j})\in\mathbb{R}^{(n)} such that MX = 0 and such that Xi,j = 0 whenever i = j or M_{i,j}\neq 0.

This graph parameter is minor monotone:

If H is a minor of G then \mu(H)\leq\mu(G).

This parameter allows an algebraic characterization of some topological properties:

  • \mu(G)\leq 1 if and only if G is a disjoint union of paths;
  • \mu(G)\leq 2 if and only if G is outerplanar;
  • \mu(G)\leq 3 if and only if G is planar;
  • \mu(G)\leq 4 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.


This combinatorics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../c/o/l/Colin_de_Verdi%C3%A8re_graph_invariant_f1c6.html"