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