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 γmaj(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.
['I. Sahul Hamid', 'S. Anandha Prabhavathy']
Majority reinforcement number