On Network Hubs

Abstract

Consider a network G = (V, E), where V denotes the set of vertices in G, and E denotes the set of edges in G. A vertex in G is said to be a source if it is only incident with outgoing edges, and a sink if it is only incident with incoming edges. Often, a source or sink is referred to as a terminal vertex. A non-terminal vertex is said to be a hub if its degree is greater than or equal to 3. In this paper, we are primarily concerned with the minimum number of hubs needed when certain constraints on the flow demand between multiple pairs of sources and sinks are imposed. The flow demand constraints considered in this paper will be in terms of the vertex-cuts between pairs of sources and sinks. This can be justified by a vertex version of the max-flow min-cut theorem [1], which states that for a network with infinite edge-capacity and unit vertex-capacity, the maximum flow between one source and one sink is equal to the minimum vertex-cut between them. Here, we remark that with appropriately modified setup, our results can be stated in terms of edge-cuts as well.