Computing Geodetic Bases of Chordal and Split Graphs

Aaron L.Douthat1, Man C.Kong1
1Department of Electrical Engineering and Computer Science The University of Kansas Lawrence, Kansas 66045

Abstract

The \({geodetic\; cover}\) of a graph \(G = (V, E)\) is a set \(C \subseteq V\) such that any vertex not in \(C\) is on some shortest path between two vertices of \(C\). A minimum geodetic cover is called a \({geodetic\; basis}\), and the size of a geodetic basis is called the \({geodetic \;number}\). Recently, Harary, Loukakis, and Tsouros announced that finding the geodetic number of a graph is NP-Complete. In this paper, we prove a stronger result, namely that the problem remains NP-Complete even when restricted to chordal graphs. We also show that the problem of computing the geodetic number for split graphs is solvable in polynomial time.