On the null space of a Colin de Verdière matrix
Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 1017-1026.

Soit G=(V,E) un graphe planaire 3-connexe, avec V={1,...,n}. Soit M=(m i,j ) une matrice symétrique n×n ayant exactement une valeur propre <0 (de multiplicité 1), telle que, pour toute arête {i,j}, m i,j <0 et, si {i,j} n’est pas une arête, m i,j =0, et supposons que le rang de M soit n-3. Alors le noyau kerM de M définit un plongement de G dans S 2 de la façon suivante : soit {a,b,c} une base de kerM ; pour iV, on pose φ(i):=(a i ,b i ,c i ) T  ; alors φ(i)0, et ψ(i):=φ(i)/φ(i) est un plongement de V dans S 2 . Si on connecte, pour toute paire de sommets adjacents i,j, les points ψ(i) et ψ(j) par une géodésique minimisante dans S 2 , on obtient un plongement de G dans S 2 .

Nous prouvons des résultats analogues pour les graphes extérieurs planaires et pour les chemins. Ces résultats s’appliquent aux matrices associées à l’invariant μ(G) introduit par Y. Colin de Verdière.

Let G=(V,E) be a 3-connected planar graph, with V={1,...,n}. Let M=(m i,j ) be a symmetric n×n matrix with exactly one negative eigenvalue (of multiplicity 1), such that for i,j with ij, if i and j are adjacent 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 kerM of M gives an embedding of G in S 2 as follows: let {a,b,c} be a basis of kerM, and for iV let φ(i):=(a i ,b i ,c i ) T ; then φ(i)0, and ψ(i):=φ(i)/φ(i) embeds V in S 2 such that connecting, for any two adjacent vertices i,j, the points ψ(i) and ψ(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 the matrices associated with the parameter μ(G) introduced by Y. Colin de Verdière.

@article{AIF_1999__49_3_1017_0,
     author = {Lov\'asz, L\'aszlo and Schrijver, Alexander},
     title = {On the null space of a {Colin} de {Verdi\`ere} matrix},
     journal = {Annales de l'Institut Fourier},
     pages = {1017--1026},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {49},
     number = {3},
     year = {1999},
     doi = {10.5802/aif.1703},
     mrnumber = {2000h:05064},
     zbl = {0923.05038},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/aif.1703/}
}
TY  - JOUR
AU  - Lovász, Lászlo
AU  - Schrijver, Alexander
TI  - On the null space of a Colin de Verdière matrix
JO  - Annales de l'Institut Fourier
PY  - 1999
SP  - 1017
EP  - 1026
VL  - 49
IS  - 3
PB  - Association des Annales de l’institut Fourier
UR  - http://archive.numdam.org/articles/10.5802/aif.1703/
DO  - 10.5802/aif.1703
LA  - en
ID  - AIF_1999__49_3_1017_0
ER  - 
%0 Journal Article
%A Lovász, Lászlo
%A Schrijver, Alexander
%T On the null space of a Colin de Verdière matrix
%J Annales de l'Institut Fourier
%D 1999
%P 1017-1026
%V 49
%N 3
%I Association des Annales de l’institut Fourier
%U http://archive.numdam.org/articles/10.5802/aif.1703/
%R 10.5802/aif.1703
%G en
%F AIF_1999__49_3_1017_0
Lovász, Lászlo; Schrijver, Alexander. On the null space of a Colin de Verdière matrix. Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 1017-1026. doi : 10.5802/aif.1703. http://archive.numdam.org/articles/10.5802/aif.1703/

[1] 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 [English translation: 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, 137-147]. | MR | Zbl

[2] H. Van Der Holst, A short proof of the planarity characterization of Colin de Verdière, Journal of Combinatorial Theory, Series B, 65 (1995), 269-272. | MR | Zbl

[3] H. Van Der Holst, Topological and Spectral Graph Characterizations, Ph.D. Thesis, University of Amsterdam, 1996.

[4] H. Van Der Holst, L. Lovász, A. Schrijver, On the invariance of Colin de Verdière's graph parameter under clique sums, Linear Algebra and its Applications, 226 (1995), 509-517. | MR | Zbl

[5] L. Lovász, A. Schrijver, A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proceedings of the American Mathematical Society, 126 (1998), 1275-1285. | MR | Zbl

Cité par Sources :