Premium
On the tree representation of chordal graphs
Author(s) -
Shibata Yukio
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120313
Subject(s) - chordal graph , combinatorics , mathematics , block graph , split graph , interval graph , treewidth , clique sum , outerplanar graph , distance hereditary graph , discrete mathematics , clique graph , indifference graph , graph , pathwidth , line graph , 1 planar graph , graph power
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 g k ( 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.