M CS The hub number of a graph

Let G be a graph; a hub set H of G is a set of vertices with the property that for any pair of vertices outside of H, there is a path between them with all intermediate vertices in H. The hub number h(G) is then defined to be the size of a smallest hub set of G. In this paper the hub number for several classes of graphs is computed; bounds in terms of other graph parameters are also determined. 1 Hub sets in graphs In what follows all graphs may be assumed to be simple; for notation and standard definitions see [2]. Imagine that we have a graph G which represents the buildings in a large industrial complex, with an edge between two buildings if it is an easy walk from one to the other. The corporation is considering implementing a rapid-transit system, and wants to place its stations in buildings (which will then be used only for this purpose) so that to travel between two non-adjacent buildings (whic