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 条

[1] Comment on "Analogies Between the Geodetic Number and the Steiner Number of Some Classes of Graphs"
John, J.
FILOMAT, 2023, 37 (02) : 585 - 589
[2] On the geodetic hull number of Pk-free graphs
Dourado, Mitre C.
Penso, Lucia D.
Rautenbach, Dieter
THEORETICAL COMPUTER SCIENCE, 2016, 640 : 52 - 60
[3] On the geodetic number of permutation graphs
Yi E.
Journal of Applied Mathematics and Computing, 2014, 46 (1-2) : 395 - 406
[4] Graphs with Large Geodetic Number
Ahangar, Hossein Abdollahzadeh
Kosari, Saeed
Sheikholeslami, Seyed Mahmoud
Volkmann, Lutz
FILOMAT, 2015, 29 (06) : 1361 - 1368
[5] Graphs with Large Steiner Number
John, J.
Raj, M. S. Malchijah
UKRAINIAN MATHEMATICAL JOURNAL, 2024, 76 (05) : 805 - 815
[6] On the geodetic number of median graphs
Bregar, Bostjan
Horvat, Aleksandra Tepeh
DISCRETE MATHEMATICS, 2008, 308 (18) : 4044 - 4051
[7] The geodetic number of the lexicographic product of graphs
Bresar, Bostjan
Sumenjak, Tadeja Kraner
Tepeh, Aleksandra
DISCRETE MATHEMATICS, 2011, 311 (16) : 1693 - 1698
[8] THE GEODETIC DOMINATION NUMBER FOR THE PRODUCT OF GRAPHS
Chellathurai, S. Robinson
Vijaya, S. Padma
TRANSACTIONS ON COMBINATORICS, 2014, 3 (04) : 19 - 30
[9] Total Restrained Geodetic Number of Graphs
Hossein Abdollahzadeh Ahangar
Maryam Najimi
Iranian Journal of Science and Technology, Transactions A: Science, 2017, 41 : 473 - 480
[10] Graphs with Large Total Geodetic Number
Ahangar, Hossein Abdollahzadeh
FILOMAT, 2017, 31 (13) : 4297 - 4304

← 1 2 3 4 5 →