The hub number of co-comparability graphs

A set H⊆VH⊆V is a hub set of a graph G=(V,E)G=(V,E) if, for every pair of vertices u,v∈V∖Hu,v∈V∖H, either u is adjacent to v or there exists a path from u to v such that all intermediate vertices are in H. The hub number of G  , denoted by h(G)h(G), is the minimum size of a hub set in G. The connected hub number of G  , denoted by hc(G)hc(G), is the minimum size of a connected hub set in G  . In this paper, we prove that h(G)=hc(G)h(G)=hc(G) for co-comparability graphs G   and characterize the case for which γc(G)=hc(G)γc(G)=hc(G) in this class of graphs, where γc(G)γc(G) denotes the connected domination number of G  . We also show that h(G)h(G) can be computed in O(|V|)O(|V|) time for trapezoid graphs and in O(|V|3)O(|V|3) time for co-comparability graphs.