On the null space of a Colin de Verdiere matrix

Citation
L. Lovasz et A. Schrijver, On the null space of a Colin de Verdiere matrix, ANN I FOUR, 49(3), 1999, pp. 1017
Citations number
5
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
ANNALES DE L INSTITUT FOURIER
ISSN journal
0373-0956 → ACNP
Volume
49
Issue
3
Year of publication
1999
Database
ISI
SICI code
0373-0956(1999)49:3<1017:OTNSOA>2.0.ZU;2-K
Abstract
Let G = (V, E) be a 3-connected planar graph, with V = {1,...,n}. Let M = ( m(i,j)) be a symmetric n x n matrix with exactly one negative eigenvalue (o f multiplicity 1), such that for i, j with i not equal j, if i and j are ad jacent then m(i,j) < 0 and if i and j are nonadjacent then m(i,j) = 0; and such that M has rank n - 3. Then the null space ker M of M gives an embeddi ng of G in S-2 as follows : let {a, b, c} be a basis of ker M, and for i is an element of V let phi(i) := (a(i), b(i), c(i))(T); then phi(i) not equal 0, and psi(i) := phi(i)/parallel to phi(i)parallel to embeds V in S-2 such that connecting, for any two adjacent vertices i,j, the points psi(i) and psi(j) by a shortest geodesic on S-2, gives a proper embedding of G in S-2. We prove similar results for outerplanar graphs and paths. They apply to th e matrices associated with the parameter mu(G) introduced by Y. Colin de Ve rdiere.