A two-valued function f: V → {-1, +1} defined on the vertices of a graph G = (V, E),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 v ∈ V, f(N[v]) > 1, where N[v] consists of v and every vertex adjacent to v. The majority domination number of a graph G, denoted 7maj (G), is the minimum value of ∑v∈V(G) f(v) over all majority dominating functions f of G. The majority reinforcement number of G, denoted by Rmaj(G), is defined to be the minimum cardinality |F| of a set F of edges such that γmaj(G + F) < γmaj(G). In this paper, we initiate the study of majority reinforcement number and determine the exact values of Rmaj for paths and cycles.
展开▼
