DIMACS TR: 2001-07

Finding a maximum stable set in pentagraphs

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


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