DIMACS TR: 2003-26

Algorithmic aspects of REducing Pseudopath Method

Author: Igor Zverovich


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