Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653880 | European Journal of Combinatorics | 2012 | 24 Pages |
Abstract
We investigate the properties of chordal graphs that follow from the well-known fact that chordal graphs admit tree representations. In particular, we study the structure of reduced clique graphs which are graphs that canonically capture all tree representations of chordal graphs. We propose a novel decomposition of reduced clique graphs based on two operations: edge contraction and removal of the edges of a split. Based on this decomposition, we characterize asteroidal sets in chordal graphs, and discuss chordal graphs that admit a tree representation with a small number of leaves.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michel Habib, Juraj Stacho,