✦ LIBER ✦

Majority domination in graphs

✍ Scribed by Izak Broere; Johannes H. Hattingh; Michael A. Henning; Alice A. McRae

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 538 KB
Volume: 138
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00194-n

No coin nor oath required. For personal study only.

✦ Synopsis

A two-valued function f defined on the vertices of a graph G =(V, E), f: V ~I-1, 1}, is a majority dominating function if the sum of its function values over at least half the closed neighborhoods is at least one. That is, for at least half the vertices ve V, f (N[v])~ 1, where N [ v ] consists of v and every vertex adjacent to v. The weight of a majority dominating function is f(V) =~f(v), over all vertices ve V. The majority domination number of a graph G, denoted 7m~j(G), equals the minimum weight of a majority dominating function of G. In this paper we present properties of the majority domination number and establish its value for various classes of graphs. We show that the decision problem corresponding to the problem of computing ~maj(G) is NP-complete.

📜 SIMILAR VOLUMES

Generalized domination and efficient dom

Generalized domination and efficient domination in graphs

✍ D.W. Bange; A.E. Barkauskas; L.H. Host; P.J. Slater 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 516 KB

This paper generalizes dominating and efficient dominating sets of a graph. Let G be a graph with vertex set V(G). If f: V(G) ~ Y, where Y is a subset of the reals, the weight off is the sum of f(v) over all ve V(G). If the closed neighborhood sum off(v) at every vertex is at least 1, thenfis called

Paired-domination in graphs

✍ Haynes, Teresa W.; Slater, Peter J. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 3 views

In a graph G Å (V, E) if we think of each vertex s as the possible location for a guard capable of protecting each vertex in its closed neighborhood N[s], then ''domination'' requires every vertex to be protected. Thus, S ʚ V (G) is a dominating set if ʜ s √ S N[s] Å V (G). For total domination, eac

Set domination in graphs

✍ E. Sampathkumar; L. Pushpa Latha 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## Abstract Let __G__ = (__V, E__) be a connected graph. A set __D__ ⊂ __V__ is a __set‐dominating set__ (sd‐set) if for every set __T__ ⊂ __V__ − __D__, there exists a nonempty set __S__ ⊂ __D__ such that the subgraph 〈__S__ ∪ __T__〉 induced by __S__ ∪ __T__ is connected. The set‐domination number

Total domination in graphs

✍ E. J. Cockayne; R. M. Dawes; S. T. Hedetniemi 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 374 KB

Factor domination in graphs

✍ Robert C. Brigham; Ronald D. Dutton 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 656 KB

Given a factoring of a graph, the factor domination number yr is the smallest number of nodes which dominate all factors. General results, mainly involving bounds on yr for factoring of arbitrary graphs, are presented, and some of these are generalizations of well known relationships. The special c

Domination-balanced graphs

✍ Charles Payan; Nguyen Huy Xuong 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## Abstract A set __D__ of vertices in a graph is said to be a dominating set if every vertex not in __D__ is adjacent to some vertex in __D.__ The domination number β(__G__) of a graph __G__ is the size of a smallest dominating set. __G__ is called domination balanced if its vertex set can be part