The leafage of a chordal graph
In-Jen Lin, Terry A. McKee, Douglas B. West · Discussiones Mathematicae Graph Theory · 1998
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.