The vertex leafage of chordal graphs
Every chordal graph G G can be represented as the intersection graph of a collection of subtrees of a host tree, a so-called tree model  of G G . This representation is not necessarily unique. The leafage ?(G) ? ( G ) of a chordal graph G G is the minimum number of leaves of the host tree of a tree model of G G . The leafage is known to be polynomially computable. In this contribution, we introduce and study the vertex leafage . The vertex leafage v?(G) v ? ( G ) of a chordal graph G G is the smallest number k k such that there exists a tree model of G G in which every subtree has at most k k leaves. In particular, the case v?(G)?2 v ? ( G ) ? 2 coincides with the class of path graphs (vertex intersection graphs of paths in trees). We prove for every fixed k?3 k ? 3 that deciding whether the vertex leafage of a given chordal graph is at most k k is NP-complete. In particular, we show that the problem is NP-complete on split graphs with vertex leafage of at most k+1 k + 1 . We further prove that it is NP-hard to find for a given split graph G G (with vertex leafage at most three) a tree model with minimum total number leaves in all subtrees, or where maximum number of subtrees are paths. On the positive side, for chordal graphs of leafage at most ? ? , we show that the vertex leafage can be calculated in time nO(?) n O ( ? ) . Finally, we prove that every chordal graph G G admits a tree model that realizes both the leafage and the vertex leafage of G G . Notably, for every path graph G G , there exists a path model with ?(G) ? ( G ) leaves in the host tree and we describe an O(n3) O ( n 3 ) time algorithm to compute such a path model.
leafage chordal graph tree model path graph clique tree