On the tree representation of chordal graphs
Yukio Shibata · Journal of Graph Theory · 1988
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.