G-2005-89
On Pitfalls in Computing the Geodetic Number of a Graph
et référence BibTeX
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.
Paru en novembre 2005 , 15 pages
Ce cahier a été révisé en septembre 2006
Axe de recherche
Applications de recherche
Document
G-2005-89.pdf (130 Ko)