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
相关论文
共 50 条
  • [1] On pitfalls in computing the geodetic number of a graph
    Pierre Hansen
    Nikolaj van Omme
    Optimization Letters, 2007, 1 : 299 - 307
  • [2] On the geodetic number of a graph
    Chartrand, G
    Harary, F
    Zhang, P
    NETWORKS, 2002, 39 (01) : 1 - 6
  • [3] On the detour number and geodetic number of a graph
    Chartrand, G
    Johns, GL
    Zhang, P
    ARS COMBINATORIA, 2004, 72 : 3 - 15
  • [4] Edge geodetic number of a graph
    Santhakumaran, A. P.
    John, J.
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2007, 10 (03): : 415 - 432
  • [5] The Total Geodetic Number of a Graph
    Ahangar, H. Abdollahzadeh
    Samodivkin, Vladimir
    UTILITAS MATHEMATICA, 2016, 100 : 253 - 268
  • [6] THE LINEAR GEODETIC NUMBER OF A GRAPH
    Santhakumaran, A. P.
    Jebaraj, T.
    Chandran, S. V. Ullas
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2011, 3 (03) : 357 - 368
  • [7] DOUBLE GEODETIC NUMBER OF A GRAPH
    Santhakumaran, A. P.
    Jebaraj, T.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2012, 32 (01) : 109 - 119
  • [8] The upper connected geodetic number and forcing connected geodetic number of a graph
    Santhakumaran, A. P.
    Titus, P.
    John, J.
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (07) : 1571 - 1580
  • [9] THE UPPER EDGE GEODETIC NUMBER AND THE FORCING EDGE GEODETIC NUMBER OF A GRAPH
    Santhakumaran, A. P.
    John, J.
    OPUSCULA MATHEMATICA, 2009, 29 (04) : 427 - 441
  • [10] The Outer Connected Geodetic Number of a Graph
    K. Ganesamoorthy
    D. Jayanthi
    Proceedings of the National Academy of Sciences, India Section A: Physical Sciences, 2021, 91 : 195 - 200
12345