×

The leafage of a chordal graph. (English) Zbl 0912.05053

A graph is chordal if it is representable as intersection graph of a family of subtrees of a host tree; see F. Gavril [J. Comb. Theory, Ser. B 16, 47-56 (1974; Zbl 0256.05101)]. The leafage \(l(G)\) of a chordal graph \(G\) is the minimum number of leaves of the host tree in such a representation. The proper leafage \(l^*(G)\) is the minimum number of leaves when no subtree may contain another. Several upper and lower bounds for \(l(G)\) and \(l^*(G)\) are proved. Especially, the maximum leafage of a chordal graph on \(n\) vertices is the maximum integer \(k\) such that \[ k \leq {n-k \choose \lfloor(n-k)/2\rfloor}; \] this is \(n - \lg n - {1 \over 2}\lg\lg n + O(1)\). A subset \(A\) of the vertex set of \(G\) is called asteroidal set of \(G\), if for every vertex \(a \in A\) there is a component of \(G-N[a]\) containing all vertices of \(A\setminus\{a\}\). For every chordal graph \(G\), the leafage is at least the maximum cardinality of an asteroidal set of \(G\). On claw-free chordal graphs leafage equals proper leafage. For some classes of chordal graphs such as \(k\)-trees or block graphs exist efficient algorithms computing (proper) leafage.
Reviewer: H.Müller (Jena)

MSC:

05C75 Structural characterization of families of graphs
05C05 Trees
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv