Finding a central vertexin an HHD-free graph.pdfVIP

Discrete Applied Mathematics 131 (2003) 93–111 /locate/dam Finding a central verte xin an HHD-free graph Victor Chepoia ; ∗ , Feodor Draganb a Laboratoire d’Informatique Fondamentale, Universite d’Aix Marseille II, Faculte des Sciences de Luminy, 163, Avenue de Luminy, 13288 Marseille Cedex 8, France b Department of Computer Science, Kent State University, Kent, OH 44242, USA Received 10 November 2000; accepted 5 May 2002 Abstract In a graph G =(V; E), the eccentricity e(v) of a verte v is ma {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 ve) as induced subgraphs. We present an algorithm which nds a central verte xof a HHD-free graph in O(1:376 |V |) time, where is the maximum degree of a verte xof G. Its com- plexity 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. ? 2003 Elsevier B.V. All rights reserved. Keywords: Distances in graphs; Central vertex; Ecient algorithms; Chordal graphs; HHD-free graphs 1. Introduction The problem we address in this paper, to nd a verte xin a given graph G whose maximum distance to any verte xof G is minimized (a central vertex of G), is one of the basic facili