The hub number of a graph
Matthew C. Walsh · Opus: Research & Creativity (Indiana University – Purdue University Fort Wayne) · 2006
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 (which are not stations), one need only walk to an adjacent station, take the RTS, and walk to the desired building. The corporation would like to implement this plan as cheaply as possible, which involves converting as few buildings as possible into transit stations. Suppose that S ⊆ V (G) and let x, y ∈ V (G). An S-path between x and y is a path where all intermediate vertices are from S. (This includes the degenerate cases where the path consists of the single edge xy or a single vertex x if x = y; call such an S-path trivial.) A set S ⊆ V (G) is a hub set of G if it has the property that, for any x, y ∈ V (G) − S, there is an S-path in G between x and y. The problem in the previous paragraph can then be rephrased: what is the smallest size of a hub set in G? We shall call this the hub number of G, and denote it by h(G). It is clear that h(G) is well-defined for any G, since V (G) is a hub set. In all situations of interest, we will assume G to be connected; if G is a disconnected graph then any hub set must contain all of the vertices in all but one of the components, as well as a hub set in the remaining component. Note that if the hypothetical corporation in question wanted to find a less draconian solution that permitted buildings to remain in use for other purposes,