𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the computational complexity of upper fractional domination

✍ Scribed by Grant A. Cheston; G. Fricke; S.T. Hedetniemi; D. Pokrass Jacobs

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
769 KB
Volume
27
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the computational complexity of upper
On the computational complexity of upper total domination
✍ Qizhi Fang πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 359 KB

Let G = (V; E) be an undirected graph. Upper total domination number t (G) is the maximum cardinality over all minimal total dominating sets of G, and upper fractional total domination number t (G) is the maximum weight over all minimal total dominating functions of G. In this paper we show that: (1

Upper bounds on the paired-domination nu
Upper bounds on the paired-domination number
✍ Xue-gang Chen; Wai Chee Shiu; Wai Hong Chan πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 199 KB

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paireddomination number of G, denoted by Ξ³ pr (G). In this w

Note on complexity of computing the domi
Note on complexity of computing the domination of binary systems
✍ A.A. Chernyak; Zh.A. Chernyak πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 419 KB

The problem of computing the domination of a coherent binary system all minimal paths sets of which have equal cardinality k (k > l), is proved to be #P-complete. Some corollaries are given.