𝔖 Bobbio Scriptorium
✦   LIBER   ✦

k-Bounded classes of dominant-independent perfect graphs

✍ Scribed by Zverovich, Igor E.

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
253 KB
Volume
32
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Let Ξ±(G), Ξ³(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k β‰₯ 0, we define the following hereditary classes: Ξ±i

where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a finite forbidden induced subgraph characterization for Ξ±i(k) and Ξ±Ξ³(k) for any k β‰₯ 0. We conjecture that iΞ³(k) also has such a characterization. Up to the present, it is known only for iΞ³(0) (domination perfect graphs

πŸ“œ SIMILAR VOLUMES

k-Independence and thek-residue of a gra
k-Independence and thek-residue of a graph
✍ Jelen, Frank πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 282 KB πŸ‘ 1 views

Favaron, Mahéo, and Saclé proved that the residue of a simple graph G is a lower bound on its independence number α(G). For k ∈ N, a vertex set X in a graph is called k-independent, if the subgraph induced by X has maximum degree less than k. We prove that a generalization of the residue, the k-resi

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 πŸ‘ 1 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

On equality in an upper bound for domina
On equality in an upper bound for domination parameters of graphs
✍ Favaron, O.; Mynhardt, C. M. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 141 KB πŸ‘ 1 views

We consider the well-known upper bounds Β΅(G) ≀ |V (G)|-βˆ†(G), where βˆ†(G) denotes the maximum degree of G and Β΅(G) the irredundance, domination or independent domination numbers of G and give necessary and sufficient conditions for equality to hold in each case. We also describe specific classes of gr