𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on the complexity of minimum dominating set

✍ Scribed by Fabrizio Grandoni

Book ID
108167506
Publisher
Elsevier Science
Year
2006
Tongue
English
Weight
92 KB
Volume
4
Category
Article
ISSN
1570-8667

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An independent dominating set in the com
An independent dominating set in the complement of a minimum dominating set of a tree
✍ Michael A. Henning; Christian LΓΆwenstein; Dieter Rautenbach πŸ“‚ Article πŸ“… 2010 πŸ› Elsevier Science 🌐 English βš– 267 KB

We prove that for every tree T of order at least 2 and every minimum dominating set D of T which contains at most one endvertex of T , there is an independent dominating set I of T which is disjoint from D. This confirms a recent conjecture of Johnson, Prier, and Walsh.

Vertices contained in every minimum domi
Vertices contained in every minimum dominating set of a tree
✍ Mynhardt, C. M. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 321 KB

In this article we begin the study of the vertex subsets of a graph G which consist of the vertices contained in all, or in no, respectively, minimum dominating sets of G. We characterize these sets for trees, and also obtain results on the vertices contained in all minimum independent dominating se

On minimum intersection of two minimum d
On minimum intersection of two minimum dominating sets of interval graphs
✍ Chang Maw-Shang; Hsu Chung-Chang πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 748 KB

This paper gives linear-time algorithms for finding two minimum (connected) dominating sets with minimum intersection for interval graphs.