I am interested in the complexity of the dominating set problem (DSP) in some specific graph classes which are subclasses of chordal graphs.
A graph is an undirected path graph if it is the vertex-intersection graph of a family of paths in some undirected tree. Let UP be the class of undirected path graphs.
A graph is an EPT graph if it is the edge-intersection graph of a family of paths in some undirected tree. An EPT graph may not be chordal, but let CEPT be the class of chordal EPT graphs.
A graph is a (rooted) directed path graph if it is the vertex-intersection graph of a family of directed paths in some rooted directed tree (i.e. all arcs directed away from the root). Let RDP be the class of (rooted) directed path graphs.
We have $RDP\subseteq CEPT \subseteq UP\subseteq chordal$
It is known that the DSP is linear-time solvable for graphs in RDP but NP-complete for graphs of UP [Booth and Johnson, 1981]
I am interested in special graphs which correspond to vertex-intersection graphs of families of undirected paths in caterpillar-like trees of maximum degree 3. More precisely, these "caterpillars" are built from a path in which each second vertex has a pendant degree-one-vertex attached to. Let us call this class cat-UP.
Moreover, my special graphs can also be constructed as the edge-intersection graphs of some families of undirected paths in specific trees of maximum degree 3.
So my questions are:
1) Is the complexity of the DSP for graphs of cat-UP known ? (note that the reduction in [Booth and Johnson, 1981] produces a host tree which is of maximum degree 3, but quite far from a caterpillar)
2) What is the complexity of DSP for graphs of CEPT ? And for graphs of CEPT arising form a host tree of maximum degree 3 ? (this is not known to ISGCI)
3) Is there any complexity result for the DSP in a closely related graph family ?