A characterization of domination perfect graphs

Zverovich, I. E.; Zverovich, V. E.; Zverovich, Igor; Zverovich, Vadim

Abstract

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobás and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K1,k ‐free graphs. It is shown that the same inequality holds for a wider class of graphs. Copyright © 1991 Wiley Periodicals, Inc., A Wiley Company

• Journal Article Type: Article
• Publication Date: Jan 1, 1991
• Journal: Journal of Graph Theory
• Print ISSN: 0364-9024
• Electronic ISSN: 1097-0118
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 15
• Issue: 2
• Pages: 109-114
• DOI: https://doi.org/10.1002/jgt.3190150202
• Public URL: https://uwe-repository.worktribe.com/output/1110369
• Publisher URL: http://dx.doi.org/10.1002/jgt.3190150202