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: doi: 10.1016/s0012-365x(98)00036-3
  • 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