|
|||||
|
|
A Characterization of Domination Reducible Graphs |
|
| Authors: | |
| Institution: | (1) RUTCOR–Rutgers Center for Operations Research, Rutgers, The State University of New Jersey, 640 Bartholomew Road, Piscataway, NJ 08854-8003, USA |
| Abstract: | We introduce a hereditary class of domination reducible graphs where the minimum dominating set problem is polynomially solvable, and characterize this class in terms of forbidden induced subgraphs.Acknowledgments The research was supported by DIMACS 2002 and 2003 Awards. The author would like to thank the both referees for their valuable suggestions.Final version received: October 3, 2003 |
| Keywords: | Domination number Hereditary class of graphs Forbidden induced subgraph Homogeneous set |
| 本文献已被 SpringerLink 等数据库收录！ | |