1998/07/03 by In-Jen Lin, Terry A. McKee, Douglas B. West
Mathematics · #math.CO #msc:05C75 #msc:05C05 #msc:05C35
published as Discussiones Mathematicae - Graph Theory 18(1998), 23-48 · 19 pages, 3 figures
arxiv created 1998/07/03 · arxiv updated 2009/11/30
The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - (1/2) lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use asteroidal sets and structural properties of chordal graphs.