Minimax Open and Closed Neighborhood Sums

Abstract

For a graph G of order |V(G)| = n and a real-valued mapping f: V(G) → ℝ, if S ⊊ V(G) then f(S) = Σ_w∊s f(w) is called the weight of S under f. The closed (respectively, open) neighborhood sum of f is the maximum weight of a closed (respectively, open) neighborhood under f, that is, NS[f] = max{f(N[v])|v ∊ V(G)} and NS(f) = max{f(N(v))|v ∊ V(G)}. We study the closed and open neighborhood sum parameter, NS[G] = min{NS[f]|f: V(G) → {1, 2,…, n} is a bijection} and NS(G) = min{NS(f)|f: V(G) → {1, 2,…, n} is a bijection}.

Keywords:

• neighborhood sum
• open neighborhood sum

2000 Mathematics Subject Classification:

• 05C78