Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion). (English) Zbl 0742.05061

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 [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\).


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C30 Enumeration in graph theory


Zbl 0251.70012
Full Text: DOI


[1] Arnold, V., Modes and quasi-modes, J. Funct. Anal., 6, 94-101 (1972) · Zbl 0251.70012
[2] Barnette, D., Map coloring, polyhedra, and the four-color problem, Dolciani Math. Exp., 8 (1983)
[3] Besson, G., Sur la multiplicité de la première valeur propre des surfaces riemanniennes, Ann. Inst. Fourier, 30, 109-128 (1980) · Zbl 0417.30033
[4] Colbois, B.; de Verdière, Y. Colin, Multiplicité de la première valeur propre du laplacien des surfaces à courbure constante, Comment. Math. Helv., 63, 194-208 (1988) · Zbl 0656.53043
[5] Cheng, S., Eigenfunctions and nodal sets, Comment. Math. Helv., 51, 43-55 (1979) · Zbl 0334.35022
[6] Chartrand, C.; Harary, Planar permutation graphs, Ann. Inst. H. Poincaré B, 3, 433-438 (1967) · Zbl 0162.27605
[7] de Verdière, Y. Colin, Spectres de variétés riemanniennes et spectres de graphes, (Proc. Intern. Congress of Math.. Proc. Intern. Congress of Math., Berkeley (1986)), 522-530 · Zbl 0693.58034
[8] de Verdière, Y. Colin, Sur la multiplicité de la première valeur propre non nulle du laplacien, Comment. Math. Helv., 61, 254-270 (1986) · Zbl 0607.53028
[9] de Verdière, Y. Colin, Sur une hypothèse de transversalité d’Arnold, Comment. Math. Helv., 63, 184-193 (1988) · Zbl 0672.58046
[10] de Verdière, Y. Colin, Constructions de laplaciens dont une partie finie du spectre est donnée, Ann. Sci. École Norm. Sup., 20, 599-615 (1987) · Zbl 0636.58036
[11] Harary, F.; Tutte, W., A dual form of Kuratowski’s theorem, Canad. Math. Bull., 8, 17-20 (1965) · Zbl 0135.42003
[12] Kuratowski, K., Sur le problème des courbes gauches en topologie, Fund. Math., 15, 271-283 (1930) · JFM 56.1141.03
[13] Kato, T., (Perturbation Theory for Linear Operators (1976), Springer-Verlag: Springer-Verlag Berlin/New York)
[14] Ore, O., (The Four-color Problem (1967), Academic Press: Academic Press New York) · Zbl 0149.21101
[15] Robertson; Seymour, Graphs minors. I, J. Combin. Theory Ser. B, 35, 39-61 (1983) · Zbl 0521.05062
[16] Tutte, W., Graph theory, Encyclopedia Math., 21 (1984) · Zbl 0554.05001
[17] White, A., Graphs, groups and surfaces (1984), North-Holland: North-Holland Amsterdam
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.