The leafage of a chordal graph
| dc.creator | Lin, In-Jen | |
| dc.creator | McKee, Terry A. | |
| dc.creator | West, Douglas B. | |
| dc.date | 1998-07-03 | |
| dc.date.accessioned | 2026-07-07T05:25:17Z | |
| dc.date.available | 2026-07-07T05:25:17Z | |
| dc.description | 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. | |
| dc.description | 19 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/math/9807022 | |
| dc.identifier | http://arxiv.org/abs/math/9807022 | |
| dc.identifier | Discussiones Mathematicae - Graph Theory 18(1998), 23-48 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/77122 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C75, 05C05, 05C35 | |
| dc.title | The leafage of a chordal graph | |
| dc.type | text |