𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On weakly connected domination in graphs

✍ Scribed by Jean E. Dunbar; Jerrold W. Grossman; Johannes H. Hattingh; Stephen T. Hedetniemi; Alice A. McRae

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
497 KB
Volume
167-168
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A weakly connected dominating set for a connected graph is a dominating set D of vertices of the graph such that the edges not incident to any vertex in D do not separate the graph. This paper considers the weakly connected domination number, 7w, and related domination parameters. It is shown that the problem of computing 7w is NP-hard in general but linear for trees. In addition, several sharp upper and lower bounds for 7w are obtained.

πŸ“œ SIMILAR VOLUMES

Connected domination critical graphs
Connected domination critical graphs
✍ Xue-Gang Chen; Liang Sun; De-Xiang Ma πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 339 KB
Permutation graphs: Connected domination
Permutation graphs: Connected domination and Steiner trees
✍ Charles J. Colbourn; Lorna K. Stewart πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 702 KB

Efficient algorithms are developed for finding a minimum cardinality connected dominating set and a minimum cardinality Steiner tree in permutation graphs. This contrasts with the known NP-completeness of both problems on comparability graphs in general.

Codiameters of 3-connected 3-domination
Codiameters of 3-connected 3-domination critical graphs
✍ Yaojun Chen; Feng Tian; Bing Wei πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 110 KB

## Abstract A graph __G__ is 3‐domination critical if its domination number Ξ³ is 3 and the addition of any edge decreases Ξ³ by 1. Let __G__ be a 3‐connected 3‐domination critical graph of order __n__. In this paper, we show that there is a path of length at least __n__βˆ’2 between any two distinct ve