Name
Abstract | ||
|---|---|---|
An ( h , s , t ) -representation of a graph G consists of a collection of subtrees of a tree T , where each subtree corresponds to a vertex of G such that (i) the maximum degree of T is at most h , (ii) every subtree has maximum degree at most s , (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T . The class of graphs that has an ( h , s , t ) -representation is denoted by h , s , t ] .An undirected graph G is called a V P T graph if it is the vertex intersection graph of a family of paths in a tree. Thus, h , 2 , 1 ] graphs are the V P T graphs that can be represented in a tree with maximum degree at most h . In this paper we characterize h , 2 , 1 ] graphs using chromatic number. We show that the problem of deciding whether a given V P T graph belongs to h , 2 , 1 ] is NP-complete, while the problem of deciding whether the graph belongs to h , 2 , 1 ] - h - 1 , 2 , 1 ] is NP-hard. Both problems remain hard even when restricted to V P T ¿ S p l i t . Additionally, we present a non-trivial subclass of V P T ¿ S p l i t in which these problems are polynomial time solvable. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.dam.2013.08.004 | Discrete Applied Mathematics |
Keywords | Field | DocType |
non-trivial subclass,graph g,vpt graph,chromatic number,subtree corresponds,maximum degree,corresponding subtrees,bounded degree tree,undirected graph,polynomial time solvable,vertex intersection graph | Discrete mathematics,Block graph,Graph toughness,Combinatorics,Graph power,Neighbourhood (graph theory),Degree (graph theory),Symmetric graph,1-planar graph,Mathematics,Pancyclic graph | Journal |
Volume | Issue | ISSN |
162 | C | 0166-218X |
Citations | PageRank | References |
3 | 0.47 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Liliana Alcón | 1 | 59 | 14.43 |
| Marisa Gutierrez | 2 | 18 | 6.59 |
| M. P. Mazzoleni | 3 | 12 | 4.05 |