The leafage of a chordal graph

Details The leafage of a chordal graph The leafage of a chordal graph

1998-07-03

arxiv.org/abs/math/9807022v1

Discussiones Mathematicae - Graph Theory 18(1998), 23-48

Mathematics

Combinatorics

19 pages, 3 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The leafage of a chordal graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The leafage of a chordal graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The leafage of a chordal graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-428885