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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom