Article ID Journal Published Year Pages File Type
4652585 Electronic Notes in Discrete Mathematics 2011 6 Pages PDF
Abstract

Chordal and dually chordal graphs possess characteristic tree representations, namely, clique trees and compatible trees, respectively. The following problem is studied: given a chordal graph G, it has to be determined if the clique trees of G are exactly the compatible trees of K(G). This does not always happen. A necessary and sufficient condition so that it is true, in terms of the minimal vertex separators of the graph, is found.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics