Hub Number (2006)

Originators: Peter Hamburger, Chris Vandell, Matt Walsh    (presented by West - REGS 2007)

Definitions: A vertex subset S is dominating if every vertex outside S has a neighbor in S. A vertex subset S is a hub if every two vertices outside S are joined by a path whose internal vertices all belong to S. The domination number γ(G) is the minimum size of a dominating set. The hub number h(G) is the minimum size of a hub. The word "connected" is applied to each definition (and subscript "c" to the parameters) when the subgraph induced by S is connected.

Background: Hub number was introduced in [W]. This paper proves several elementary bounds on hub number and connected hub number, gives a characterization of graphs for which h(G) = h_c(G) = 1, and computes both parameters for several classes of graphs. It also proves that the problem of deciding whether a graph G has a (connected) hub of size k is NP- complete.

Several bounds on h(G) and h_c(G) are easily shown:

• h(G) ≤ h_c(G) ≤ γ_c(G) (Every connected dominating set is a hub.)
• h(G) ≥diam(G)-1
• γ_c(G) ≤ h_c(G)+1 (Kinnersley) (The vertices outside the neighborhood of a smallest connected hub S form a clique and are all adjacent to every neighbor of S. Hence adding any neighbor of S yields a connected dominating set.)
• γ(G) ≤ h(G)+1 (Worah) (Same argument, without "connected".)

During the 2007 REGS, various subsets of {Grauman, Hartke, Jobson, Kinnersley, West, Wiglesworth, Worah, Wu} in [GHJKWWWW] showed that γ_c(G) ≤ h(G) + 1. Together with the first bound above, this implies that h(G) ≤ h_c(G) ≤ γ_c(G) ≤ h(G) + 1. Together with the complexity results about approximating the connected domination number, the implies that approximating the hub number or the connected hub number within a factor of lnD-cln lnD is NP-hard even on the family of bipartite graphs with maximum degree at most D.

The paper [GHJKWWWW] further characterized the graphs such that γ_c(G) > h_c(G) ≥ 4 as graphs obtained by substituting graphs into three consecutive vertices of a cycle (a complete graph must be substituted into the middle vertex of the three). This characterization yields a polynomial-time algorithm to check whether h _c(G) = γ_c(G). The conclusion is that the hub number and connected hub number are not much different from the connected domination number.

Problem 1: Characterize the graphs for which h(G) = h_c (G).

[GHJKWWWW] shows that h(G) < h_c(G) only when h_c(G) = γ_c(G). It would also suffice to characterize the graphs such that h(G) = γ_c(G).

References:
[CC] M. Chlebík and J. Chlebíková, Approximation hardness of dominating set problems. In {\it Algorithms---ESA 2004, Lecture Notes in Comput. Sci.} 3221 (Springer, Berlin, 2004), 192--203.
[GHJKWWWW] Grauman, Tracy; Hartke, Stephen G.; Jobson, Adam; Kinnersley, Bill; West, Douglas B.; Wiglesworth, Lesley; Worah, Pratik; Wu, Hehui. The Hub Number of a Graph. Info. Proc. Lett., to appear.
[W] Walsh, Matthew. The hub number of a graph. Int. J. Math. Comput. Sci. 1 (2006), no. 1, 117--124.