Upper domination and upper irredundance perfect graphs

Gutin, Gregory; Zverovich, Vadim

Abstract

Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) = IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result. © 1998 Elsevier Science B.V. All rights reserved.

• Journal Article Type: Article
• Publication Date: Aug 28, 1998
• Deposit Date: Sep 24, 2015
• Publicly Available Date: Feb 19, 2016
• Journal: Discrete Mathematics
• Print ISSN: 0012-365X
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 190
• Issue: 1-3
• Pages: 95-105
• DOI: https://doi.org/10.1016/S0012-365X%2898%2900036-3
• Keywords: independence number, upper domination number, upper irredundance number
• Public URL: https://uwe-repository.worktribe.com/output/1099501
• Publisher URL: http://dx.doi.org/10.1016/S0012-365X(98)00036-3
• Contract Date: Feb 19, 2016