
arXiv: math/9807022
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.
19 pages, 3 figures
Extremal problems in graph theory, chordal graph, asteroidal set, FOS: Mathematics, Mathematics - Combinatorics, Structural characterization of families of graphs, Combinatorics (math.CO), subtree intersection representation, leafage, 05C75, 05C05, 05C35, Trees
Extremal problems in graph theory, chordal graph, asteroidal set, FOS: Mathematics, Mathematics - Combinatorics, Structural characterization of families of graphs, Combinatorics (math.CO), subtree intersection representation, leafage, 05C75, 05C05, 05C35, Trees
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 35 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
