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 条

[21] Algorithmic upper bounds for graph geodetic number
Ahmad T. Anaqreh
Boglárka G.-Tóth
Tamás Vinkó
Central European Journal of Operations Research, 2022, 30 : 1221 - 1237
[22] OPERATION ON TOTAL OUTER-INDEPENDENT GEODETIC NUMBER OF A GRAPH
Bhavyavenu, K. L.
Venkanagouda, M. Goudar
ADVANCES AND APPLICATIONS IN MATHEMATICAL SCIENCES, 2019, 18 (06): : 469 - 485
[23] An O(mn2) Algorithm for Computing the Strong Geodetic Number in Outerplanar Graphs
Mezzini, Mauro
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2022, 42 (02) : 591 - 599
[24] On the geodetic number of permutation graphs
Yi E.
Journal of Applied Mathematics and Computing, 2014, 46 (1-2) : 395 - 406
[25] On the geodetic number of median graphs
Bregar, Bostjan
Horvat, Aleksandra Tepeh
DISCRETE MATHEMATICS, 2008, 308 (18) : 4044 - 4051
[26] Graphs with Large Geodetic Number
Ahangar, Hossein Abdollahzadeh
Kosari, Saeed
Sheikholeslami, Seyed Mahmoud
Volkmann, Lutz
FILOMAT, 2015, 29 (06) : 1361 - 1368
[27] Geodetic Number of Powers of Cycles
Abudayah, Mohammad
Alomari, Omar
Al Ezeh, Hassan
SYMMETRY-BASEL, 2018, 10 (11):
[28] On the geodetic number of complementary prisms
Castonguay, Diane
Coelho, Erika M. M.
Coelho, Hebert
Nascimento, Julliano R.
INFORMATION PROCESSING LETTERS, 2019, 144 : 39 - 42
[29] The geodetic number of the lexicographic product of graphs
Bresar, Bostjan
Sumenjak, Tadeja Kraner
Tepeh, Aleksandra
DISCRETE MATHEMATICS, 2011, 311 (16) : 1693 - 1698
[30] The Edge Geodetic Number of Product Graphs
Anand, Bijo S.
Changat, Manoj
Chandran, S. V. Ullas
ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2018, 2018, 10743 : 143 - 154

← 1 2 3 4 5 →