### G-2005-89

# On Pitfalls in Computing the Geodetic Number of a Graph

## Pierre Hansen and Nikolaj van Omme

Given a simple connected graph *G = (V,E)* the geodetic closure *I [S]* *V* of a
subset *S* of *V* is the union of all sets of nodes lying on some geodesic (or shortest
path) joining a pair of nodes *v _{k}, v_{l}*

*V*. The geodetic number, denoted by

*g(G)*, is the smallest cardinality of a node set

*S*

*such that*

*I [S**] = V*. In "The geodetic number of a graph",

*Mathematical and Computer Modelling*17 (June 1993) 89–95, F. Harary, E. Loukakis and C. Tsouros propose an incorrect algorithm to find the geodetic number of a graph

*G*. We provide counterexamples and show why the proposed approach must fail. We then develop a 0-1 integer programming model to find the geodetic number. Computational results are given.

Published **November 2005**
,
15 pages

This cahier was revised in **September 2006**