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. 1425. doi:10.1016/j.dam.2012.12.006
Research output not available from this repository, contact author.
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 socalled 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 NPcomplete. In particular, we show that the problem is NPcomplete on split graphs with vertex leafage of at most k+1. We further prove that it is NPhard 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 > Mathematics  
Journal or Publication Title:  Discrete Applied Mathematics  
Publisher:  Elsevier Science Ltd.  
ISSN:  0166218X  
Official Date:  11 May 2014  
Dates: 


Volume:  Volume 168  
Page Range:  pp. 1425  
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 