## DIMACS TR: 2001-07

## Finding a maximum stable set in pentagraphs

### Authors: I. E. Zverovich and I. I. Zverovich

**
ABSTRACT
**

*Penta* is the configuration shown in Figure 1(a), where
continuous lines represent edges and dotted lines represent non-edges.
The vertex $u$ in Figure 1(a) is called the *center* of Penta.
A graph $G$ is called a *pentagraph* if every induced subgraph $H$
of $G$ has a vertex $v$ which is not a center of induced Penta in $H$.

The class of pentagraphs is a common generalization of chordal (triangulated)
graphs and Mahadev graphs.

We construct a polynomial-time algorithm that either find a maximum stable
set of $G$ or concludes that $G$ is not a pentagraph.

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

DIMACS Home Page