Authors

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.