𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Multiplicities of Eigenvalues and Tree-Width of Graphs

✍ Scribed by Yves Colin de Verdière

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
567 KB
Volume
74
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Tree-width and circumference of graphs
Tree-width and circumference of graphs
✍ Etienne Birmele 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 37 KB

## Abstract We prove that every graph of circumference __k__ has tree‐width at most __k__ − 1 and that this bound is best possible. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 24–25, 2003

Eigenvalue multiplicities of highly symm
Eigenvalue multiplicities of highly symmetric graphs
✍ Paul Terwilliger 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 905 KB

We find we prove: lower kunds on eigenvalue multiplicities for highly symmetric graphs. In partictiar ## I.. If r is distance-regular with valency k and girth g (g 2 4). and A (A # *k) IS an eigenvalue of r, then the multiplicity of h is at least k(& - #e/41-1 if g=O or 1 ,'mod 4), 2( k -1)["4' i

Efficient Parallel Algorithms for Graphs
Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
✍ Jens Lagergren 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 236 KB

We present an efficient parallel algorithm for the tree-decomposition problem Ž 3 . Ž. for fixed width w. The algorithm runs in time O O log n and uses O O n processors on an ARBITRARY CRCW PRAM. The sequential complexity of our tree-decom-Ž 2 . position algorithm is O O n log n . The tree-decomposi

Optimal Parametric Search on Graphs of B
Optimal Parametric Search on Graphs of Bounded Tree-Width
✍ David Fernández-Baca; Giora Slutzki 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 339 KB

We give linear-time algorithms for a class of parametric search problems on weighted graphs of bounded tree-width. We also discuss the implications of our results to approximate parametric search on planar graphs.

Ka,k Minors in Graphs of Bounded Tree-Wi
Ka,k Minors in Graphs of Bounded Tree-Width
✍ Thomas Böhme; John Maharry; Bojan Mohar 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 175 KB

It is shown that for any positive integers k and w there exists a constant N ¼ N ðk; wÞ such that every 7-connected graph of tree-width less than w and of order at least N contains K 3;k as a minor. Similar result is proved for K a;k minors where a is an arbitrary fixed integer and the required conn