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

Let graph \(G\) have vertex set \(\{1,2,\dots,n\}\), and let \({\mathcal M}(G)\) be the set of symmetric \(n\times n\) matrices \(M= (m_{i,j})\) such that: (i) \(M\) has exactly one negative eigenvalue, of multiplicity 1; (ii) for all \(i\), \(j\) with \(i\neq j\), one has: (a) \(m_{i,j}= 0\), if \(i\) and \(j\) are nonadjacent; (b) \(m_{i,j}< 0\), if \(i\) and \(j\) are adjacent. The main result of this paper is that if \(G\) is 3-connected and planar, then for any matrix \(M\in{\mathcal M}(G)\) of corank 3, the null space \(\ker M\) of \(M\) gives an imbedding of \(G\) in the 2-sphere. The authors also show that: (1) if \(G\) is a path, then for any matrix \(M\in{\mathcal M}(G)\) of corank 1, the null space \(\ker M\) of \(M\) gives an imbedding of \(G\) in the line; (2) if \(G\) is 2-connected and outerplanar, then for any matrix \(M\in{\mathcal M}(G)\) of corank 2, the null space \(\ker M\) of \(M\) gives a representation of \(G\) as a convex polygon with non-crossing diagonals. These three results are related to a parameter introduced by \textit{Y. Colin de Verdière} [J. Comb. Theory, Ser. B 50, No. 1, 11-21 (1990; Zbl 0742.05061)].

Recommendations

Cites work

Cited in

(19)

This page was built for publication: On the null space of a Colin de Verdière matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1296155)