Abstract
For a graph G of order |V(G)| = n and a real-valued mapping \({f:V(G)\rightarrow\mathbb{R}}\), if \({S\subset V(G)}\) then \({f(S)=\sum_{w\in 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]={\rm max}\{f(N[v])|v \in V(G)\}}\) and \({NS(f)={\rm max}\{f(N(v))|v \in V(G)\}}\). The closed (respectively, open) lower neighborhood sum of f is the minimum weight of a closed (respectively, open) neighborhood under f, that is, \({NS^{-}[f]={\rm min}\{f(N[v])|v\in V(G)\}}\) and \({NS^{-}(f)={\rm min}\{f(N(v))|v\in V(G)\}}\). For \({W\subset \mathbb{R}}\), the closed and open neighborhood sum parameters are \({NS_W[G]={\rm min}\{NS[f]|f:V(G)\rightarrow W}\) is a bijection} and \({NS_W(G)={\rm min}\{NS(f)|f:V(G)\rightarrow W}\) is a bijection}. The lower neighbor sum parameters are \({NS^{-}_W[G]={\rm max}NS^{-}[f]|f:V(G)\rightarrow W}\) is a bijection} and \({NS^{-}_W(G)={\rm max}NS^{-}(f)|f:V(G)\rightarrow W}\) is a bijection}. For bijections \({f:V(G)\rightarrow \{1,2,\ldots,n\}}\) we consider the parameters NS[G], NS(G), NS −[G] and NS −(G), as well as two parameters minimizing the maximum difference in neighborhood sums.
Similar content being viewed by others
References
Jinnah, M.I.: On sigma labelled graphs. In: Acharya, B.D., Hegde, S.M. (eds.) Proc. of Group Discussion on Graph Labelling Problems, pp. 71–77 (2003)
O’Neal, A., Slater, P.J.: The minimax, maximin, and spread values for open neighborhood sums for 2-regular graphs. Cong. Num. (to appear)
Schneider A., Slater P.J.: Minimax neighborhood sums. Congr. Numer. 188, 75–83 (2007)
Schneider A., Slater P.J.: Minimax open and closed neighborhood sums. AKCE J. Graphs Comb. 6(1), 183–190 (2009)
Singh, T., Rao, B., Parameswaran, V.: Some sigma labeled graphs. In: Acharya, B.D., Arumugam, S., Rao, S.B. (eds.) Graphs, Combinatorics, Algorithms and Applications. Narosa Publishing House, New Delhi, pp. 125–133 (2004)
Vilfred, V.: Perfectly regular graphs or cyclically regular graphs, sigma labelled graphs and partitions. Proc. Srinivasa Ramanujan Centenary Celebration International Conference in Mathematics (1987)
Vilfred, V.: Sigma labelled graphs and circulant graphs, Ph.D. Thesis, University of Kerala, Trivandrum, India (1994)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
O’Neal, A., Slater, P.J. An Introduction to Closed/Open Neighborhood Sums: Minimax, Maximin, and Spread. Math.Comput.Sci. 5, 69–80 (2011). https://doi.org/10.1007/s11786-011-0075-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11786-011-0075-4