ContributionsUpper domination and upper irredundance perfect graphs |
| |
Authors: | Gregory Gutin and Vadim E. Zverovich |
| |
Affiliation: | a Department of Mathematics and Statistics, Brunel University, Uxbridge, Middlesex UB8 3PH, UK b Department II of Mathematics, RWTH Aachen, Aachen 52056, Germany |
| |
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. |
| |
Keywords: | Independence number Upper domination number Upper irredundance number |
本文献已被 ScienceDirect 等数据库收录! |
|