Groupe d’études et de recherche en analyse des décisions


On Pitfalls in Computing the Geodetic Number of a Graph


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

Ce cahier a été révisé en septembre 2006