Soit un graphe planaire 3-connexe, avec . Soit une matrice symétrique ayant exactement une valeur propre (de multiplicité 1), telle que, pour toute arête , et, si n’est pas une arête, , et supposons que le rang de soit . Alors le noyau de définit un plongement de dans de la façon suivante : soit une base de ; pour , on pose ; alors , et est un plongement de dans . Si on connecte, pour toute paire de sommets adjacents , les points et par une géodésique minimisante dans , on obtient un plongement de dans .
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 introduit par Y. Colin de Verdière.
Let be a 3-connected planar graph, with . Let be a symmetric matrix with exactly one negative eigenvalue (of multiplicity 1), such that for with , if and are adjacent then and if and are nonadjacent then , and such that has rank . Then the null space of gives an embedding of in as follows: let be a basis of , and for let ; then , and embeds in such that connecting, for any two adjacent vertices , the points and by a shortest geodesic on , gives a proper embedding of in .
We prove similar results for outerplanar graphs and paths. They apply to the matrices associated with the parameter 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}, volume = {49}, year = {1999}, pages = {1017-1026}, doi = {10.5802/aif.1703}, mrnumber = {2000h:05064}, zbl = {0923.05038}, language = {en}, url = {http://dml.mathdoc.fr/item/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) pp. 1017-1026. doi : 10.5802/aif.1703. http://gdmltest.u-ga.fr/item/AIF_1999__49_3_1017_0/
[1] 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] 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] Topological and Spectral Graph Characterizations, Ph.D. Thesis, University of Amsterdam, 1996.
,[4] 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] 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
, ,