Computing Geodetic Bases of Chordal and Split Graphs

The \emph{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 \emph{geodetic basis}, and the size of a geodetic basis is called the \emph{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.