Research work · 1988
On the tree representation of chordal graphs
Yukio Shibata
Journal of Graph Theory
Abstract
Abstract We introduce the notion of the boundary clique and the k‐overlap clique graph and prove the following: Every incomplete chordal graph has two nonadjacent simplicial vertices lying in boundary cliques. An incomplete chordal graph G is k‐connected if and only if the k‐overlap clique graph gk(G) is connected. We give an algorithm to construct a clique tree of a connected chordal graph and characterize clique trees of connected chordal graphs using the algorithm.