Dominating and large induced trees in regular graphs (Q2463903): Difference between revisions

\textit{X. Chen} et al. [Ars Comb. 73, 193--203 (2004; Zbl 1112.05317)] asked for characterization of the class of graphs and the class of regular graphs that have an induced dominating tree. The present paper shows that the corresponding decision problems are NP-complete. A forbidden induced subgraph condition is given for the existence of induced dominating trees. Tight lower bounds are given on the maximum order of induced trees in connected cacti of maximum degree 3 and connected cubic graphs.