The hub number of co-comparability graphs ?
A set H?V H ? V is a hub set of a graph G=(V,E) G = ( V , E ) if, for every pair of vertices u,v?V?H u , 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) h c ( G ) , is the minimum size of a connected hub set in G . In this paper, we prove that h(G)=hc(G) h ( G ) = h c ( G ) for co-comparability graphs G  and characterize the case for which ?c(G)=hc(G) ? c ( G ) = h c ( 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.
hub number co-comparability graph connected hub number dominating set