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.

DOI: 10.1002/jgt.3190120313