Print

Nordle, Sarah Anne

Mathematics

2005

MS

A widely studied parameter in graph theory is the independence number of a graph: the maximum size of a set of vertices, no two of which are of distance one. We extend this concept to allow picking points in the interiors of edges, keeping the requirement that points lie a distance at least x apart using the natural metric on edges. Let B(G, x) denote the maximum size of such a set. We consider B as a function of x for a fixed graph G. We call this the bean function, which we picture as packing beans of diameter x on G. We determine B(G, x) exactly for several classes of graphs including balanced binary trees, complete graphs, and complete bipartite graphs. The function is surprisingly subtle even for these natural classes. We also give a general result about the bean function for an arbitrary tree.