A note on the geodetic number and the Steiner number of AT-free graphs

被引：0

作者：

Hon, Wing-Kai ^{[1
]}

Kloks, Ton ^{[1
]}

Liu, Hsiang-Hsuan ^{[2
]}

Wang, Hung-Lung ^{[3
]}

Wang, Yue-Li ^{[4
]}

机构：

[1] Natl Tsing Hua Univ, Dept Comp Sci, Hsinchu, Taiwan

[2] Univ Utrecht, Dept Informat & Comp Sci, Utrecht, Netherlands

[3] Natl Taiwan Normal Univ, Dept Comp Sci & Informat Engn, Taipei, Taiwan

[4] Natl Taiwan Univ Sci & Technol, Dept Informat Management, Taipei, Taiwan

来源：

THEORETICAL COMPUTER SCIENCE | 2021年 / 854卷

关键词：

AT-free graph; Geodetic number; Steiner number;

D O I：

10.1016/j.tcs.2020.12.010

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study two graph parameters, namely the geodetic number and the Steiner number, which are related to the concept of convexity. We show that, in asteroidal triple-free graphs, the Steiner number is greater than or equal to the geodetic number. This answers a question posed by Hernando, Jiang, Mora, Pelayo, and Seara in 2005. Besides, we show that the gap between the two parameters can be arbitrarily large even in unit-interval graphs, a proper subclass of AT-free graphs. (C) 2020 Elsevier B.V. All rights reserved.

引用

页码：131 / 135

页数：5

共 50 条

[21] Strong Geodetic Number of Complete Bipartite Graphs and of Graphs with Specified Diameter
Irsic, Vesna
GRAPHS AND COMBINATORICS, 2018, 34 (03) : 443 - 456
[22] Strong Geodetic Number of Complete Bipartite Graphs, Crown Graphs and Hypercubes
Gledel, Valentin
Irsic, Vesna
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2020, 43 (03) : 2757 - 2767
[23] Strong Geodetic Number of Complete Bipartite Graphs and of Graphs with Specified Diameter
Vesna Iršič
Graphs and Combinatorics, 2018, 34 : 443 - 456
[24] On the detour number and geodetic number of a graph
Chartrand, G
Johns, GL
Zhang, P
ARS COMBINATORIA, 2004, 72 : 3 - 15
[25] The edge Steiner number of a graph
Santhakumaran, A. P.
John, J.
JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2007, 10 (05) : 677 - 696
[26] On the geodetic number and related metric sets in Cartesian product graphs
Bresar, Bostjan
Klavzar, Sandi
Horvat, Aleksandra Tepeh
DISCRETE MATHEMATICS, 2008, 308 (23) : 5555 - 5561
[27] On the vertex monophonic, vertex geodetic and vertex Steiner numbers of graphs
John, J.
ASIAN-EUROPEAN JOURNAL OF MATHEMATICS, 2021, 14 (10)
[28] THE UPPER EDGE GEODETIC NUMBER AND THE FORCING EDGE GEODETIC NUMBER OF A GRAPH
Santhakumaran, A. P.
John, J.
OPUSCULA MATHEMATICA, 2009, 29 (04) : 427 - 441
[29] The upper connected geodetic number and forcing connected geodetic number of a graph
Santhakumaran, A. P.
Titus, P.
John, J.
DISCRETE APPLIED MATHEMATICS, 2009, 157 (07) : 1571 - 1580
[30] Geodetic number and domination number of Γ(R(+)M)
Al-Labadi, Manal
Almuhur, Eman Mohammad
Audeh, Wasim
Al-boustanji, Anwar
BOLETIM SOCIEDADE PARANAENSE DE MATEMATICA, 2025, 43

← 1 2 3 4 5 →