On the null space of a Colin de Verdière matrix

Lovász, Lászlo ; Schrijver, Alexander

Annales de l'Institut Fourier, Tome 49 (1999), p. 1017-1026 / Harvested from Numdam

Résumé

Soit $G=(V,E)$ un graphe planaire 3-connexe, avec $V=\lbrace 1,\ldots ,n\rbrace $. Soit $M=(m_{i,j})$ une matrice symétrique $n\times n$ ayant exactement une valeur propre $< 0$ (de multiplicité 1), telle que, pour toute arête $\lbrace i,j\rbrace $, $m_{i,j}< 0$ et, si $\lbrace i ,j \rbrace $ n’est pas une arête, $m_{i,j}=0$, et supposons que le rang de $M$ soit $n-3$. Alors le noyau $\ker M$ de $M$ définit un plongement de $G$ dans $S^2$ de la façon suivante : soit $\lbrace a,b,c\rbrace $ une base de $\ker M$ ; pour $i\in V$, on pose $\phi (i):=(a_i,b_i,c_i)^T$ ; alors $\phi (i)\ne 0$, et $\psi (i):=\phi (i)/\Vert \phi (i)\Vert $ est un plongement de $V$ dans $S^2$. Si on connecte, pour toute paire de sommets adjacents $i,j$, les points $\psi (i)$ et $\psi (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 $\mu (G)$ introduit par Y. Colin de Verdière.

Abstract

Let $G=(V,E)$ be a 3-connected planar graph, with $V=\lbrace 1,\ldots ,n\rbrace $. Let $M=(m_{i,j})$ be a symmetric $n\times n$ matrix with exactly one negative eigenvalue (of multiplicity 1), such that for $i,j$ with $i\ne j$, 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 $\ker M$ of $M$ gives an embedding of $G$ in $S^2$ as follows: let $\lbrace a,b,c\rbrace $ be a basis of $\ker M$, and for $i\in V$ let $\phi (i):=(a_i,b_i,c_i)^T$; then $\phi (i)\ne 0$, and $\psi (i):=\phi (i)/\Vert \phi (i)\Vert $ 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 the matrices associated with the parameter $\mu (G)$ introduced by Y. Colin de Verdière.

Détail

Publié le : 1999-01-01

MR 2000h:05064 | Zbl 0923.05038

DOI : https://doi.org/10.5802/aif.1703

Bibliographie

[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 91m:05068 | Zbl 0742.05061

[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 96g:05050 | Zbl 0841.05025

[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 97e:05113 | Zbl 0834.05036

[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 98j:05059 | Zbl 0886.05055