On a property of minimal triangulations |
| |
Authors: | Dieter Kratsch |
| |
Institution: | a LITA, Université Paul Verlaine-Metz, 57045 Metz Cedex 01, France b School of Computing, University of Leeds, Leeds, LS2 9JT, United Kingdom |
| |
Abstract: | A graph H has the property MT, if for all graphs G, G is H-free if and only if every minimal (chordal) triangulation of G is H-free. We show that a graph H satisfies property MT if and only if H is edgeless, H is connected and is an induced subgraph of P5, or H has two connected components and is an induced subgraph of 2P3.This completes the results of Parra and Scheffler, who have shown that MT holds for H=Pk, the path on k vertices, if and only if k?5 A. Parra, P. Scheffler, Characterizations and algorithmic applications of chordal graph embeddings, Discrete Applied Mathematics 79 (1997) 171-188], and of Meister, who proved that MT holds for ?P2, ? copies of a P2, if and only if ??2 D. Meister, A complete characterisation of minimal triangulations of 2K2-free graphs, Discrete Mathematics 306 (2006) 3327-3333]. |
| |
Keywords: | Chordal graph Minimal triangulation Minimal separator |
本文献已被 ScienceDirect 等数据库收录! |
|