Premium
k ‐separator chordal graphs: leafage and subfamilies
Author(s) -
Markenzon Lilian,
Pereira Paulo Renato da Costa,
Waga Christina F. E. M.
Publication year - 2013
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2012.00875.x
Subject(s) - chordal graph , interval graph , combinatorics , treewidth , split graph , mathematics , indifference graph , pathwidth , discrete mathematics , graph , 1 planar graph , line graph
The leafage of a chordal graph G is the minimum number of leaves among the clique‐trees of G . In this paper, based on properties of the minimal vertex separators, the leafage of a k ‐separator chordal graph is determined in linear time. This result allows establishment of the relationship of some subfamilies of chordal graphs, such as k ‐trees, interval and uniquely representable chordal graphs.