An Algorithm To Find The Core Of A \(CV\)-Graph

The core of a graph was defined by Morgan and Slater [MS80] as a path in the graph minimizing the sum of the distance of all vertices of the graph from the path. A linear algorithm to find the core of a tree has been given in [MS80]. For the general graph the problem can be shown to be NP-hard using a reduction from the Hamiltonian path problem.
A graph with no chordless cycle of length exceeding three is called a chordal graph. Every chordal graph is the intersection graph of a family of subtrees of a tree. The intersection graph of a family of undirected paths of a tree is called a UV graph. The intersection graph of an edge disjoint family of paths of a tree is called a CV graph [AAPX91]. We have characterised that the CV graphs are nothing but block graphs. CV graphs form a proper subclass of UV graphs which in turn form a proper subclass of chordal graphs.
In this paper, we present an \( {O}(ne)\) algorithm to find the core of a CV graph, where \(n\) is the number of vertices and \(e\) is the number of edges.