Neighborhood Sums in Graphs

Dr. Peter Slater

Department of Mathematical Sciences
UA Huntsville

January 30, 2009
219 Shelby Center
3:00 (Refreshements at 2:30)

Abstract

Given a set of charged particles in a domain such as a ring or a surface such as a sphere, the particles will "equally space" themselves. If the charges on the particles are not uniform, one still expects a balanced spacing. That is, one expects not to see a large total charge concentrated near any one point.

To construct a k-by-k magic square, one arranges the numbers 1,2,...,k² in a k-by-k matrix so that all row and column sums are equal. Again, one is assigning specified point masses so that the weights are equally spread out.

A neighborhood sum problem considered here is to assign the weights in a given set W to the vertices of a graph G so as to minimize the maximum sum of weights in any one neighborhood. Other problems considered are to maximize the minimum such sum and to minimize the spread of these values.