Article ID Journal Published Year Pages File Type
4653880 European Journal of Combinatorics 2012 24 Pages PDF
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
, ,