DIMACS TR: 2003-26
Algorithmic aspects of REducing Pseudopath Method
Author: Igor Zverovich
ABSTRACT
Let G and H be graphs. A substitution of H in G instead of a vertex v
in V (G) is the graph G(v -> H), which consists of disjoint union of
H and G - v with the additional edge-set {xy : x in V (H); y in NG
(v)}. For a hereditary class of graphs P, the substitutional closure of
P is defined as the class P* consisting of all graphs which can be
obtained from graphs in P by repeated substitutions.
Let P be an arbitrary hereditary class for which a characterization in
terms of forbidden induced subgraphs is known. Zverovich [20] proposed
Reducing Pseudopath Method for constructing a forbidden induced
subgraph characterization of P* . However, an implementation of the
method is not straightforward.
We find conditions that guarantee the existence of a very simple
reducing pseudopath [for example, of length 1]. As a result, a number
of known and new characterizations may be obtained immediately by
applying the improved method. In particular, we essentially simplify
proofs given in Brandstadt, Hoang, and Zverovich [3]. As examples, we
consider some interesting hereditary classes.
AMS Subject Classification: 05C75, 05C99.
Keywords: Hereditary class, forbidden induced subgraph, substitutional
closure, stability number.
Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-26.ps.gz
DIMACS Home Page