Dominating and large induced trees in regular graphs (Q2463903)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5218426
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Dominating and large induced trees in regular graphs |
scientific article; zbMATH DE number 5218426 |
Statements
Dominating and large induced trees in regular graphs (English)
0 references
6 December 2007
0 references
\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.
0 references
induced dominating tree
0 references
regular graph
0 references
cactus
0 references
0.8039430975914001
0 references
0.76167893409729
0 references
0.7573501467704773
0 references
0.7512640953063965
0 references
