Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651141 | Discrete Mathematics | 2007 | 5 Pages |
Abstract
We give a characterization, in terms of forbidden induced subgraphs, of those graphs in which every connected induced subgraph has a dominating induced path on at most k vertices (k⩾3k⩾3). We show, in particular, that k=4k=4 means precisely the class of domination-reducible graphs, whose original definition applied four types of structural reduction.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
G. Bacsó, Zs. Tuza, M. Voigt,