The vertex leafage of chordal graphs

Details The vertex leafage of chordal graphs The vertex leafage of chordal graphs

2011-04-13

arxiv.org/abs/1104.2524v2

Computer Science

Discrete Mathematics

Scientific paper

Every chordal graph $G$ can be represented as the intersection graph of a collection of subtrees of a host tree, a so-called {\em tree model} of $G$. The leafage $\ell(G)$ of a connected chordal graph $G$ is the minimum number of leaves of the host tree of a tree model of $G$. The vertex leafage $\vl(G)$ is the smallest number $k$ such that there exists a tree model of $G$ in which every subtree has at most $k$ leaves. The leafage is a polynomially computable parameter by the result of \cite{esa}. In this contribution, we study the vertex leafage. We prove for every fixed $k\geq 3$ that deciding whether the vertex leafage of a given chordal graph is at most $k$ is NP-complete by proving a stronger result, namely that the problem is NP-complete on split graphs with vertex leafage of at most $k+1$. On the other hand, for chordal graphs of leafage at most $\ell$, we show that the vertex leafage can be calculated in time $n^{O(\ell)}$. Finally, we prove that there exists a tree model that realizes both the leafage and the vertex leafage of $G$. Notably, for every path graph $G$, there exists a path model with $\ell(G)$ leaves in the host tree and it can be computed in $O(n^3)$ time.

Affiliated with

Also associated with

No associations

Rating

The vertex leafage of chordal graphs 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 vertex leafage of chordal graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The vertex leafage of chordal graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-219128