The Library
The vertex leafage of chordal graphs
Tools
Chaplick, Steven and Stacho, Juraj (2014) The vertex leafage of chordal graphs. Discrete Applied Mathematics, Volume 168 . pp. 14-25. doi:10.1016/j.dam.2012.12.006 ISSN 0166-218X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.dam.2012.12.006
Abstract
Every chordal graph G can be represented as the intersection graph of a collection of subtrees of a host tree, a so-called tree model of G. This representation is not necessarily unique. The leafage ℓ(G) of a chordal graph G is the minimum number of leaves of the host tree of a tree model of G. The leafage is known to be polynomially computable.
In this contribution, we introduce and study the vertex leafage. The vertex leafage vℓ(G) of a chordal graph G is the smallest number k such that there exists a tree model of G in which every subtree has at most k leaves. In particular, the case vℓ(G)≤2 coincides with the class of path graphs (vertex intersection graphs of paths in trees).
We prove for every fixed k≥3 that deciding whether the vertex leafage of a given chordal graph is at most 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. We further prove that it is NP-hard to find for a given split graph 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(ℓ).
Finally, we prove that every chordal graph G admits 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 ℓ(G) leaves in the host tree and we describe an O(n3) time algorithm to compute such a path model.
Item Type: | Journal Article | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||||||||
Publisher: | Elsevier Science Ltd. | ||||||||||
ISSN: | 0166-218X | ||||||||||
Official Date: | 11 May 2014 | ||||||||||
Dates: |
|
||||||||||
Volume: | Volume 168 | ||||||||||
Page Range: | pp. 14-25 | ||||||||||
DOI: | 10.1016/j.dam.2012.12.006 | ||||||||||
Status: | Peer Reviewed | ||||||||||
Publication Status: | Published | ||||||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |