TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1993

COGA 5-Wheel

Page Content

to Navigation

Preprints 1993

Triangulating Graphs without Asteroidal Triples
Citation key Report-365-1993
Author Rolf H. Möhring
Pages 281-287
Year 1993
Journal Discrete Applied Mathematics, 1996
Volume 64
Number 365
Institution Technische Universität Berlin, Institut für Mathematik
Abstract An asteroidal triple\/ of a graph $G$ is a triple of mutually independent vertices such that, between any two of them, there exists a path that avoids the neighbourhood of the third. A triangulation of $G$ is a chordal graph $H$ on the same vertex set that contains $G$ as a subgraph, i. e., $V(G) = V(H)$ and $E(G) \subseteq E(H)$. We show that every ⊆-minimal triangulation of a graph $G$ without asteroidal triples is already an interval graph\/. This implies that the treewidth\/ of a graph $G$ without asteroidal triples equals its pathwidth\/. Another consequence is that the minimum number of additional edges in a triangulation of $G$ ( fill-in\/) equals the minimum number of edges needed to embed $G$ into an interval graph ( interval completion number\/). The proof is based on the interesting property that a minimal cover of all induced cycles of a graph $G$ without asteroidal triples by chords does not introduce new asteroidal triples. These results complement recent results by Corneil et al. about the linear structure of graphs without asteroidal triples.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe