×

zbMATH — the first resource for mathematics

Multiplicities of eigenvalues and tree-width of graphs. (English) Zbl 1027.05064
Summary: Using multiplicities of eigenvalues of elliptic self-adjoint differential operators on graphs and transversality, we construct some new invariants of graphs which are related to tree-width.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bacher, R.; Colin de Verdière, Y., Multiplicités de valeurs propres et transformations étoile-triangle des graphes, Bull. soc. math. France, 123, 101-117, (1995) · Zbl 0845.05068
[2] Cheng, S.Y., Eigenfunctions and nodal sets, Comment. math. helv., 51, 43-55, (1976) · Zbl 0334.35022
[3] Cohen-Tannoudji, C.; Diu, B.; Laloë, F., Mécanique quantique I, (1977), Hermann Paris
[4] Colin de Verdière, Y., Sur un nouvel invariant des graphes et un critère de planarité, J. combin. theory ser. B, 50, 11-21, (1990) · Zbl 0742.05061
[5] Colin de Verdière, Y., A new graph invariant and a criterion for planarity, Graph structure theory, Amer. math. soc. colloq. publ., 147, (1991), Amer. Math. Soc Providence, p. 137-148 · Zbl 0791.05024
[6] Colin de Verdière, Y., Réseaux électriques planaires, I, Comment. math. helv., 69, 351-374, (1994) · Zbl 0816.05052
[7] Colin de Verdière, Y., Multiplicités de valeurs propres: laplaciens discrets et laplaciens continus, Rend. mat. 7, 13, 433-460, (1993) · Zbl 0802.58060
[8] Y. Colin de Verdière, Spectres des graphes, Institut Fourier, Grenoble, 1995
[9] Y. Colin de Verdière, Discrete magnetic Schrödinger operators and tree-width of graphs, Institut Fourier, Grenoble, 308, 1995
[10] Colin de Verdière, Y., Spectre d’opérateurs différentiels sur LES graphes, Proceedings, conference on random walks and discrete potential theory, (1997), Cortona
[11] Colin de Verdière, Y.; Gitler, I.; Vertigan, D., Réseaux électriques planaires, II, Comment. math. helv., 71, 144-167, (1996) · Zbl 0853.05074
[12] Colin de Verdière, Y.; Torki, N., Opérateur de Schrödinger avec champs magnétiques, Sém. théor. spectrale Géom. (Grenoble), 11, 9-18, (1993) · Zbl 0937.35510
[13] Y. Colin de Verdière, Y. Pan, B. Ycart, Singular limits of Schrödinger operators and Markov processes, J. Operator Theory
[14] Duistermaat, J., Fourier integral operators, (1996), Birkhäuser Basel · Zbl 0841.35137
[15] Guillemin, V.; Pollack, A., Differential topology, (1974), Prentice-Hall New York · Zbl 0361.57001
[16] van der Holst, H., A short proof of the planarity characterization of Colin de Verdière, J. combin. theory ser. B, 65, 269-272, (1995) · Zbl 0841.05025
[17] van der Holst, H., Topological and spectral graph characterizations, (1996), Amsterdam University
[18] H. van der Holst, Graphs with magnetic Schrödinger operators of low corank, 1997
[19] Lieb, E.; Loss, M., Fluxes, Laplacians and Kasteleyn’s theorem, Duke math. J., 71, 337-363, (1993) · Zbl 0787.05083
[20] L. Lovász, A. Schrijver, A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
[21] Nadirashvili, N., Berger’s isoperimetric problem and minimal immersions of surfaces, Geom. funct. anal., 6, 877-897, (1996) · Zbl 0868.58079
[22] Robertson, N.; Seymour, P., Graphs minors. III. planar tree-width, J. combin. theory ser. B, 36, 49-64, (1984) · Zbl 0548.05025
[23] Robertson, N.; Seymour, P., Graphs minors. IV. tree-width and well quasi-ordering, J. combin. theory ser. B, 48, 227-254, (1990) · Zbl 0719.05032
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.