TY - JOUR
T1 - A note on the geodetic number and the Steiner number of AT-free graphs
AU - Hon, Wing Kai
AU - Kloks, Ton
AU - Liu, Hsiang Hsuan
AU - Wang, Hung Lung
AU - Wang, Yue Li
N1 - Publisher Copyright:
© 2020 Elsevier B.V.
PY - 2021/1/16
Y1 - 2021/1/16
N2 - 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.
AB - 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.
KW - AT-free graph
KW - Geodetic number
KW - Steiner number
UR - http://www.scopus.com/inward/record.url?scp=85097798357&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097798357&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2020.12.010
DO - 10.1016/j.tcs.2020.12.010
M3 - Article
AN - SCOPUS:85097798357
VL - 854
SP - 131
EP - 135
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -