## Upper domination and upper irredundance perfect graphs

Article English OPEN
Gutin, Gregory ; Zverovich, Vadim E. (1998)
• Publisher: Elsevier BV
• Journal: Discrete Mathematics, volume 190, issue 1-3, pages 95-105 (issn: 0012-365X)
• Related identifiers:
• Subject: Theoretical Computer Science | Discrete Mathematics and Combinatorics

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.
• References (10)

[1] G.A. Cheston and G. Fricke, Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance. Discrete Appl. Math. 55 (1994) 241-258.

[2] E.J. Cockayne, O. Favaron, C. Payan and A.G. Thomason, Contributions to the theory of domination, independence and irredundance in graphs. Discrete Math. 33 (1981) 249-258.

[3] M.C. Golumbic and R.C. Laskar, Irredundancy in circular arc graphs. Discrete Appl. Math. 44 (1993) 79-89.

[4] P.L. Hammer and F. Maffray, Preperfect graphs. Combinatorica 13 (1993) 199-208.

[5] M.A. Henning, Irredundance perfect graphs. Discrete Math. 142 (1995) 107-120.

[6] M.S. Jacobson and K. Peters, A note on graphs which have upper irredundance equal to independence. Discrete Appl. Math. 44 (1993) 91-97.

[7] M.S. Jacobson and K. Peters, Chordal graphs and upper irredundance, upper domination and independence. Discrete Math. 86 (1990) 59-69.

[8] J. Topp, Domination, independence and irredundance in graphs. Dissertationes Math. 342 (1995) 99 pp.

[9] L. Volkmann, private communication.

[10] I.E. Zverovich and V.E. Zverovich, An induced subgraph characterization of domination perfect graphs. J. Graph Theory 20 (1995) 375-395.

• Metrics
No metrics available
Share - Bookmark