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 条

[31] On bounds for the cutting number of a graph
Mukwembi, Simon
Hove-Musekwa, Senelani Dorothy
INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 2012, 43 (06): : 637 - 649
[32] A Binding Number Computation of Graph
Han, Congying
He, Guoping
Duan, Hua
Zhang, Xuping
FIFTH INTERNATIONAL CONFERENCE ON FUZZY SYSTEMS AND KNOWLEDGE DISCOVERY, VOL 4, PROCEEDINGS, 2008, : 285 - +
[33] THE GEODETIC DOMINATION NUMBER FOR THE PRODUCT OF GRAPHS
Chellathurai, S. Robinson
Vijaya, S. Padma
TRANSACTIONS ON COMBINATORICS, 2014, 3 (04) : 19 - 30
[34] Contraction-based method for computing a lower bound on the clique number of a graph
Gueham, Assia
Ait Haddadene, Hacene
Nagih, Anass
2019 6TH INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT 2019), 2019, : 1758 - 1762
[35] Total Restrained Geodetic Number of Graphs
Hossein Abdollahzadeh Ahangar
Maryam Najimi
Iranian Journal of Science and Technology, Transactions A: Science, 2017, 41 : 473 - 480
[36] Graphs with Large Total Geodetic Number
Ahangar, Hossein Abdollahzadeh
FILOMAT, 2017, 31 (13) : 4297 - 4304
[37] Total Restrained Geodetic Number of Graphs
Ahangar, Hossein Abdollahzadeh
Najimi, Maryam
IRANIAN JOURNAL OF SCIENCE AND TECHNOLOGY TRANSACTION A-SCIENCE, 2017, 41 (A2): : 473 - 480
[38] Restrained geodetic domination of edge subdivision graph
Mulloor, John Joy
Sangeetha, V.
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2022, 14 (05)
[39] A note on the geodetic number and the Steiner number of AT-free graphs
Hon, Wing-Kai
Kloks, Ton
Liu, Hsiang-Hsuan
Wang, Hung-Lung
Wang, Yue-Li
THEORETICAL COMPUTER SCIENCE, 2021, 854 : 131 - 135
[40] PRODUCTS OF GEODESIC GRAPHS AND THE GEODETIC NUMBER OF PRODUCTS
Soloff, Jake A.
Marquez, Rommy A.
Friedler, Louis M.
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2015, 35 (01) : 35 - 42

← 1 2 3 4 5 →