Characterization of graphs dominated by induced paths

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 ⩾ 3 ). We show, in particular, that k = 4 means precisely the class of domination-reducible graphs, whose original de...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2007-04, Vol.307 (7), p.822-826
Main Authors: Bacsó, G., Tuza, Zs, Voigt, M.
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Forbidden induced subgraph
Graph domination
Graph theory
Induced path
Mathematics
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ⩾ 3 ). We show, in particular, that k = 4 means precisely the class of domination-reducible graphs, whose original definition applied four types of structural reduction.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2005.11.035