## DIMACS TR: 2001-39

## Extended $(P_5, {\overline P_5})$-free graph

### Authors: I. E. Zverovich

**
ABSTRACT
**

Let $G$ and $H$ be graphs.
A {\em substitution} of $H$ in $G$ instead of a vertex $v \in V(G)$ is
the graph $G(v \to H)$, which consists of disjoint union of $H$ and $G - v$
with the additional edge-set $\{xy: x \in V(H), y \in N_G(v)\}$.
For a hereditary class of graphs ${\mathcal P}$,
the {\em substitutional closure} of ${\mathcal P}$ is defined
as the class ${\mathcal P}^*$ consisting of all graphs which can be obtained
from graphs in $P$ by repeated substitutions.

We characterize the substitutional closure
$(P_5 \cup K_1, {\overline P_5} \cup K_1)$-free graphs in terms of forbidden
induced subgraphs.

The weighted stability problem is polynomially solvable for this class.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-39.ps.gz

DIMACS Home Page