Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion) (Q1813331): Difference between revisions

A new graph invariant \(\mu(G)\) is presented and shown to be monotonic with respect to edge-removal and an operation which includes homeomorphic reduction as a special case. Then, since \(\mu(K_ 5)=\mu(K_{3,3})=4\), Kuratowski's planarity criterion is used to show that \(G\) is planar if and only if \(\mu(G)\leq 3\). A graph is said to be \(n\)-critical if \(\mu(G)=n\) and \(\mu(G_ 1)<n\) for any proper minor \(G_ 1\) of \(G\). Then \(n\)-critical graphs for \(0\leq n\leq 4\) are enumerated, and it is proved that \(G\) is outer-planar if and only if \(\mu(G)\leq 2\). It follows from another result that if \(G\) can be embedded in an orientable surface of genus \(g\), then \(\mu(G)\leq 4g+3\). This result could conceivably be used to bound the genus of \(G\) from below if some procedure could be found to calculate, or at least bound, \(\mu(G)\). However, the definition given here of \(\mu(G)\) is highly non-constructive. Let \(O_ G\) be the set of symmetric \(n\times n\) matrices derived from the adjacency matrix of \(G\) by replacing all the 1s by negative reals and the diagonal elements by arbitrary reals. If \(A\in O_ G\), its smallest eigenvalue \(\lambda_ 1\) has multiplicity 1; let \(\lambda_ 2\) be its second-smallest eigenvaue. Then \(\mu(G)\) is the largest integer \(n _ 0\) such that there exists a matrix \(A\in O_ G\) such that \(\lambda_ 2\) has multiplicity \(n_ 0\) and satisfies the Arnold hypothesis [\textit{V. I. Arnold}, Modes and quasimodes, Funct. Anal. Appl. 6, 94-101 (1972; Zbl 0251.70012)]: \(O_ G\) and the subvariety of symmetric matrices having some eingevalue \(\lambda_ 2\) with multiplicity \(n_ 0\) intersect transversally in \(A\).