On pitfalls in computing the geodetic number of a graph

被引：6

作者：

Hansen, Pierre ^{[1
,2
]}

van Omme, Nikolaj ^{[3
,4
]}

机构：

[1] Gerad, Montreal, PQ, Canada

[2] HEC Montreal, Montreal, PQ, Canada

[3] CRT, Montreal, PQ, Canada

[4] Ecole Polytech, Montreal, PQ H3C 3A7, Canada

来源：

OPTIMIZATION LETTERS | 2007年 / 1卷 / 03期

关键词：

Graph; Geodetic number; Maximal geodetic closure; Algorithm;

D O I：

10.1007/s11590-006-0032-3

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Given a simple connected graph G = (V, E) the geodetic closure I[S] subset of 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) epsilon S. 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", [Harary et al. in Math. Comput. Model. 17: 89-95, 1993] 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.

引用

页码：299 / 307

页数：9

共 10 条

[1] On the edge geodetic number of a graph [J].