Back

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.

, 15 pages

This cahier was revised in September 2006

Research Axis

Research applications

Document

G-2005-89.pdf (100 KB)