Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: leafage

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

The leafage of a chordal graph

100%

Lin I.-J., McKee T., West D.

Discussiones Mathematicae Graph Theory

1998

tom 18

nr 1

23-48

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Lin I.-J.

1 McKee T.

1 West D.

1 1998

Wyniki wyszukiwania

The leafage of a chordal graph