## DIMACS TR: 2002-28

## The Domination Number of $(K_p, P_5)$-Free Graphs

### Authors: I. E. Zverovich

**
ABSTRACT
**

We prove that, for each $p \ge 1$, there exists
a polynomial time algorithm for finding a minimum domination
set in the class of all $(K_p, P_5)$-free graphs.

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

DIMACS Home Page