𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Independent domination in finitely defined classes of graphs

✍ Scribed by R. Boliac; V. Lozin

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
264 KB
Volume
301
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We study the independent dominating set problem restricted to graph classes deΓΏned by ΓΏnitely many forbidden induced subgraphs. The main result is two su cient conditions for the problem to be NP-hard in a ΓΏnitely deΓΏned class of graphs. We conjecture that those conditions are also necessary and describe several classes of graphs verifying the conjecture.

πŸ“œ SIMILAR VOLUMES

Independent domination in regular graphs
Independent domination in regular graphs
✍ Julie Haviland πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 387 KB

Let G be a simple graph of order n. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. Motivated by work of Cockayne et al. (1991) and Cockayne and Mynhardt (1989), we investigate the maximum value of the product of th

k-Bounded classes of dominant-independen
k-Bounded classes of dominant-independent perfect graphs
✍ Zverovich, Igor E. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 253 KB πŸ‘ 2 views

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 f

Independent perfect domination sets in C
Independent perfect domination sets in Cayley graphs
✍ Jaeun Lee πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 92 KB πŸ‘ 1 views

## Abstract In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube __Q~n~__ has an independent perfect domination set if and only if __Q~n~__ i