𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Laplace eigenvalues and bandwidth-type invariants of graphs

✍ Scribed by Martin Juvan; Bojan Mohar

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
664 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For (weighted) graphs several labeling properties and their relation to the eigenvalues of the Laplacian matrix of a graph are considered. Several upper and lower bounds on the bandwidth and other min‐sum problems are derived. Most of these bounds depend on Laplace eigenvalues of the graphs. The results are applied in the study of bandwidth and the min‐sums of random graphs, random regular graphs, and Kneser graphs. Β© John Wiley & Sons, Inc.

πŸ“œ SIMILAR VOLUMES

The edge-bandwidth of theta graphs
The edge-bandwidth of theta graphs
✍ Dennis Eichhorn; Dhruv Mubayi; Kevin O'Bryant; Douglas B. West πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 129 KB

An edge-labeling f of a graph G is an injection from E(G) to the set of integers. The edge-bandwidth of G is B H (G) min f {B H (f )}, where B H (f ) is the maximum difference between labels of incident edges of G. The theta graph Γ‚(l 1 , F F F ,l m ) is the graph consisting of m pairwise internally

Multiplicities of Eigenvalues and Tree-W
Multiplicities of Eigenvalues and Tree-Width of Graphs
✍ Yves Colin de VerdiΓ¨re πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 567 KB

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.