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 [J].

Ahangar, Hossein Abdollahzadeh ;

Kosari, Saeed ;

Sheikholeslami, Seyed Mahmoud ;

Volkmann, Lutz .

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 [J].

Centeno, C. C. ;

Penso, L. D. ;

Rautenbach, D. ;

de SA, V. G. Pereira .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (02) :717-731

[5] On the geodetic number of a graph [J].

Chartrand, G ;

Harary, F ;

Zhang, P .

NETWORKS, 2002, 39 (01) :1-6

[6] BLOCK DECOMPOSITION APPROACH TO COMPUTE A MINIMUM GEODETIC SET [J].

Ekim, Tinaz ;

Erey, Aysel .

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 [J].

FRAENKEL, AS ;

HARARY, F .

INTERNATIONAL JOURNAL OF GAME THEORY, 1989, 18 (03) :327-338

[10] THE GEODETIC NUMBER OF A GRAPH [J].

HARARY, F ;

LOUKAKIS, E ;

TSOUROS, C .

MATHEMATICAL AND COMPUTER MODELLING, 1993, 17 (11) :89-95

← 1 2 →