Sphere packing and local majorities in graphs
Nathan Linial, David Peleg, Yu. Rabinovich, Michael Saks · 2002
The paper concerns some extremal problems on packing spheres in graphs and covering graphs by spheres. Tight bounds are provided for these problems on general graphs. The bounds are then applied to answer the following question: Let f be a nonnegative function defined on the vertices of a graph G, and suppose one has a lower bound on the local averages of f, i.e., on f's average over every j-neighborhood in G for j=1,. . .,r. What can be concluded globally? I.e, what can be said about the average of f over all G? This question arose in connection with issues of locality in distributed network computation. The average estimation problem with unit radius balls is also studied for some special classes of graphs.>