Neighborhood Sums in Graphs
Dr. Peter Slater
Department of Mathematical Sciences
January 30, 2009
219 Shelby Center
3:00 (Refreshements at 2:30)
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,...,k2 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.
- Hits: 102