ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2018-2019): c. 84%
Graph Theory 18(1) (1998) 23-48DOI: 10.7151/dmgt.1061
National Ocean University, Taipei, Taiwan
Terry A. McKee
Wright State University, Dayton, OH 45435-0001, U.S.A
Douglas B. West
University of Illinois, Urbana, IL 61801-2975, U.S.A.
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 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
Keywords: chordal graph, subtree intersection representation, leafage.
1991 Mathematics Subject Classification: 05C75, 05C05, 05C35.
Received 2 January 1997
Revised 19 April 1998