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 条

[41] The geodetic hop domination number of complementary prisms
Anusha, D.
John, J.
Robin, S. Joseph
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2021, 13 (06)
[42] GEODETIC NUMBER VERSUS HULL NUMBER IN P3-CONVEXITY
Centeno, C. C.
Penso, L. D.
Rautenbach, D.
de SA, V. G. Pereira
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (02) : 717 - 731
[43] Survey of Geodetic Mapping Methods Geodetic Approaches to Mapping and the Relationship to Graph-Based SLAM
Agarwal, Pratik
Burgard, Wolfram
Stachniss, Cyrill
IEEE ROBOTICS & AUTOMATION MAGAZINE, 2014, 21 (03) : 63 - 80
[44] Computing the diversity vectors of balls of a given graph
Fedoryaeva, T., I
SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2016, 13 : 122 - 129
[45] Comment on "Analogies Between the Geodetic Number and the Steiner Number of Some Classes of Graphs"
John, J.
FILOMAT, 2023, 37 (02) : 585 - 589
[46] On the geodetic hull number of Pk-free graphs
Dourado, Mitre C.
Penso, Lucia D.
Rautenbach, Dieter
THEORETICAL COMPUTER SCIENCE, 2016, 640 : 52 - 60
[47] On the domination number of a graph
Pruchnewski, A
DISCRETE MATHEMATICS, 2002, 251 (1-3) : 129 - 136
[48] On the toll number of a graph
Dravec, Tanja
DISCRETE APPLIED MATHEMATICS, 2022, 321 : 250 - 257
[49] The Steiner number of a graph
Chartrand, G
Zhang, P
DISCRETE MATHEMATICS, 2002, 242 (1-3) : 41 - 54
[50] The geodetic-dominating number of comb product graphs
Fahrudin, Dimas Agus
Saputro, Suhadi Wido
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2020, 8 (02) : 373 - 381

← 1 2 3 4 5 →