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) no. 3, pp. 1017-1026.

Soit $G=(V,E)$ un graphe planaire 3-connexe, avec $V=\{1,...,n\}$. Soit $M=\left(m_{i,j}\right)$ une matrice symétrique $n\times 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 $i\in V$, on pose $\phi \left(i\right):=(a_i,b_i,c_i{)}^T$ ; alors $\phi \left(i\right)\ne 0$, et $\psi \left(i\right):=\phi \left(i\right)/\parallel \phi \left(i\right)\parallel$ est un plongement de $V$ dans $S^2$. Si on connecte, pour toute paire de sommets adjacents $i,j$, les points $\psi \left(i\right)$ et $\psi \left(j\right)$ 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 \left(G\right)$ introduit par Y. Colin de Verdière.

Let $G=(V,E)$ be a 3-connected planar graph, with $V=\{1,...,n\}$. Let $M=\left(m_{i,j}\right)$ 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 $kerM$ of $M$ gives an embedding of $G$ in $S^2$ as follows: let $\{a,b,c\}$ be a basis of $kerM$, and for $i\in V$ let $\phi \left(i\right):=(a_i,b_i,c_i{)}^T$; then $\phi \left(i\right)\ne 0$, and $\psi \left(i\right):=\phi \left(i\right)/\parallel \phi \left(i\right)\parallel$ embeds $V$ in $S^2$ such that connecting, for any two adjacent vertices $i,j$, the points $\psi \left(i\right)$ and $\psi \left(j\right)$ 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 \left(G\right)$ introduced by Y. Colin de Verdière.

[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