✦ LIBER ✦

Upper domination and upper irredundance perfect graphs

✍ Scribed by Gregory Gutin; Vadim E. Zverovich

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 534 KB
Volume: 190
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(98)00036-3

No coin nor oath required. For personal study only.

✦ Synopsis

Let /~(G), F(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is called

In this paper, we present a characterization of F-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of F-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of F-perfect graphs. These results imply a number of known theorems on F-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be F-perfect and IR-perfect which improves a known analogous result.

📜 SIMILAR VOLUMES

Chordal graphs and upper irredundance, u

Chordal graphs and upper irredundance, upper domination and independence

✍ Michael S. Jacobson; Ken Peters 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 648 KB

In this paper we consider the following parameters: IR(G), the upper irredundance number, which is the order of the largest maximal irredundant set, I'(G), the upper domination number, which is the order of the largest minimal dominating set and /3(G), the independence number, which is the order of

Vertex criticality for upper domination

Vertex criticality for upper domination and irredundance

✍ P. J. P. Grobler; C. M. Mynhardt 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

## Abstract Let π be any of the domination parameters __ir__ γ, __i__, β, Γ or __IR__. The graph __G__ is π‐__critical__ (π^+^‐__critical__) if the removal of any vertex of __G__ causes π(__G__) to decrease (increase). We show that the classes of __IR__‐critical and Γ‐critical graphs coincide, and

A semi-induced subgraph characterization

A semi-induced subgraph characterization of upper domination perfect graphs

✍ Zverovich, Igor E.; Zverovich, Vadim E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB 👁 2 views

Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absorbantl

The sequence of upper and lower dominati

The sequence of upper and lower domination, independence and irredundance numbers of a graph

✍ E.J. Cockayne; C.M. Mynhardt 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 803 KB

Necessary and sufficient conditions are established for the existence of a graph whose upper and lower domination, independence and irredundance numbers are six given positive integers. This result shows that the only relationships between these six parameters which hold for all graphs and which do

Domination and irredundance in cubic gra

Domination and irredundance in cubic graphs

✍ E.J. Cockayne; C.M. Mynhardt 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 552 KB

Upper total domination in claw-free grap

Upper total domination in claw-free graphs

✍ Odile Favaron; Michael A. Henning 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract A set __S__ of vertices in a graph __G__ is a total dominating set of __G__ if every vertex of __G__ is adjacent to some vertex in __S__ (other than itself). The maximum cardinality of a minimal total dominating set of __G__ is the upper total domination number of __G__, denoted by Γ~__