𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Rank inequalities for chordal graphs

✍ Scribed by Ko-Wei Lih

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
480 KB
Volume
113
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Distance Approximating Trees for Chordal
Distance Approximating Trees for Chordal and Dually Chordal Graphs
✍ Andreas BrandstΓ€dt; Victor Chepoi; Feodor Dragan πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 165 KB

In this paper we show that, for each chordal graph G, there is a tree T such that T is a spanning tree of the square G 2 of G and, for every two vertices, the distance between them in T is not larger than the distance in G plus 2. Moreover, we prove that, if G is a strongly chordal graph or even a d

Improved Bandwidth Approximation for Tre
Improved Bandwidth Approximation for Trees and Chordal Graphs
✍ Anupam Gupta πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 110 KB

A linear arrangement of an n-vertex graph G = V E is a one-one mapping f of the vertex set V onto the set n = 0 1 n -1 . The bandwidth of this linear arrangement is the maximum difference between the images of the endpoints of any edge in E G . When the input graph G is a tree, the best known approx