Article ID Journal Published Year Pages File Type
4651141 Discrete Mathematics 2007 5 Pages PDF
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
, , ,