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 条

[41] On the geodetic number of complementary prisms
Castonguay, Diane
Coelho, Erika M. M.
Coelho, Hebert
Nascimento, Julliano R.
INFORMATION PROCESSING LETTERS, 2019, 144 : 39 - 42
[42] THE VERTEX STEINER NUMBER OF A GRAPH
John, J.
TRANSACTIONS ON COMBINATORICS, 2020, 9 (02) : 115 - 124
[43] Geodetic Number of Powers of Cycles
Abudayah, Mohammad
Alomari, Omar
Al Ezeh, Hassan
SYMMETRY-BASEL, 2018, 10 (11):
[44] The Total Geodetic Number of a Graph
Ahangar, H. Abdollahzadeh
Samodivkin, Vladimir
UTILITAS MATHEMATICA, 2016, 100 : 253 - 268
[45] The total Steiner number of a graph
John, J.
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (03)
[46] The Geodetic Number for the Unit Graphs Associated with Rings of Order P and P2
Abdelkarim, Heba Adel
SYMMETRY-BASEL, 2023, 15 (09):
[47] An O(mn2) Algorithm for Computing the Strong Geodetic Number in Outerplanar Graphs
Mezzini, Mauro
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2022, 42 (02) : 591 - 599
[48] The Outer Connected Geodetic Number of a Graph
K. Ganesamoorthy
D. Jayanthi
Proceedings of the National Academy of Sciences, India Section A: Physical Sciences, 2021, 91 : 195 - 200
[49] Some remarks on the geodetic number of a graph
Dourado, Mitre C.
Protti, Fabio
Rautenbach, Dieter
Szwarcfiter, Jayme L.
DISCRETE MATHEMATICS, 2010, 310 (04) : 832 - 837
[50] The Outer Connected Geodetic Number of a Graph
Ganesamoorthy, K.
Jayanthi, D.
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES INDIA SECTION A-PHYSICAL SCIENCES, 2021, 91 (02) : 195 - 200

← 1 2 3 4 5 →