Strong Geodetic Number of Complete Bipartite Graphs and of Graphs with Specified Diameter

被引：16
作者：
Irsic, Vesna [1 ,2 ]
机构：
[1] Inst Math Phys & Mech, Ljubljana, Slovenia
[2] Univ Ljubljana, Fac Math & Phys, Ljubljana, Slovenia
来源：
GRAPHS AND COMBINATORICS | 2018年 / 34卷 / 03期
关键词：
Geodetic number; Strong geodetic number; Isometric path number; Complete bipartite graphs; Diameter;
D O I：
10.1007/s00373-018-1885-9
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The strong geodetic problem is a recent variation of the classical geodetic problem. For a graph G, its strong geodetic number is the cardinality of a smallest vertex subset S, such that each vertex of G lies on one fixed shortest path between a pair of vertices from S. In this paper, some general properties of the strong geodetic problem are studied, especially in connection with the diameter of a graph. The problem is also solved for balanced complete bipartite graphs.
引用
收藏
页码：443 / 456
页数：14
相关论文
共 20 条
  • [1] Graphs with Large Geodetic Number
    Ahangar, Hossein Abdollahzadeh
    Kosari, Saeed
    Sheikholeslami, Seyed Mahmoud
    Volkmann, Lutz
    [J]. FILOMAT, 2015, 29 (06) : 1361 - 1368
  • [2] [Anonymous], 2001, J COMBIN MATH COMBIN
  • [3] Bresar B, 2011, STRUCTURAL ANALYSIS OF COMPLEX NETWORKS, P197, DOI 10.1007/978-0-8176-4789-6_8
  • [4] GEODETIC NUMBER VERSUS HULL NUMBER IN P3-CONVEXITY
    Centeno, C. C.
    Penso, L. D.
    Rautenbach, D.
    de SA, V. G. Pereira
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (02) : 717 - 731
  • [5] On the geodetic number of a graph
    Chartrand, G
    Harary, F
    Zhang, P
    [J]. NETWORKS, 2002, 39 (01) : 1 - 6
  • [6] BLOCK DECOMPOSITION APPROACH TO COMPUTE A MINIMUM GEODETIC SET
    Ekim, Tinaz
    Erey, Aysel
    [J]. RAIRO-OPERATIONS RESEARCH, 2014, 48 (04) : 497 - 507
  • [7] Ekim T, 2012, LECT NOTES COMPUT SC, V7256, P279, DOI 10.1007/978-3-642-29344-3_24
  • [8] Fitzpatrick S. L., 1999, C NUMER, V137, P109
  • [9] GEODETIC CONTRACTION GAMES ON GRAPHS
    FRAENKEL, AS
    HARARY, F
    [J]. INTERNATIONAL JOURNAL OF GAME THEORY, 1989, 18 (03) : 327 - 338
  • [10] THE GEODETIC NUMBER OF A GRAPH
    HARARY, F
    LOUKAKIS, E
    TSOUROS, C
    [J]. MATHEMATICAL AND COMPUTER MODELLING, 1993, 17 (11) : 89 - 95
12