Finding a central vertex in an HHD-free graph

AbstractIn a graph G=(V,E), the eccentricity e(v) of a vertex v is max{d(v,u):u∈V}. The center of a graph is the set of vertices with minimum eccentricity. A house–hole–domino-free (HHD-free) graph is a graph which does not contain the house, the domino, and holes (cycles of length at least five) as induced subgraphs. We present an algorithm which finds a central vertex of a HHD-free graph in O(Δ1.376|V|) time, where Δ is the maximum degree of a vertex of G. Its complexity is linear in the case of weak bipolarizable graphs, chordal graphs, and distance-hereditary graphs. The algorithm uses special metric and convexity properties of HHD-free graphs