G-2005-89
On Pitfalls in Computing the Geodetic Number of a Graph
and BibTeX reference
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 vk, vl
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
Research Axis
Research applications
Document
G-2005-89.pdf (100 KB)