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 条
  • [31] On the geodetic number of a graph
    Chartrand, G
    Harary, F
    Zhang, P
    NETWORKS, 2002, 39 (01) : 1 - 6
  • [32] Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs
    Oellermann, Ortrud R.
    Puertas, Maria Luz
    DISCRETE MATHEMATICS, 2007, 307 (01) : 88 - 96
  • [33] Induced Disjoint Paths in AT-free graphs
    Golovach, Petr A.
    Paulusma, Daniel
    van Leeuwen, Erik Jan
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2022, 124 : 170 - 191
  • [34] ON THE COMPLEMENT CONNECTED STEINER NUMBER OF A GRAPH
    John, J.
    Raj, M. S. malchijah
    ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2021, 90 (04): : 377 - 386
  • [35] Finite groups whose coprime graphs are AT-free
    Li, Huani
    Ma, Xuanlong
    ELECTRONIC RESEARCH ARCHIVE, 2024, 32 (11): : 6443 - 6449
  • [36] ON THE HULL NUMBER OF TRIANGLE-FREE GRAPHS
    Dourado, Mitre C.
    Protti, Fabio
    Rautenbach, Dieter
    Szwarcfiter, Jayme L.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 23 (04) : 2163 - 2172
  • [37] Connected Feedback Vertex Set on AT-Free Graphs
    Mukherjee, Joydeep
    Saha, Tamojit
    COMBINATORIAL ALGORITHMS, IWOCA 2023, 2023, 13889 : 319 - 330
  • [38] Edge geodetic number of a graph
    Santhakumaran, A. P.
    John, J.
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2007, 10 (03) : 415 - 432
  • [39] DOUBLE GEODETIC NUMBER OF A GRAPH
    Santhakumaran, A. P.
    Jebaraj, T.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2012, 32 (01) : 109 - 119
  • [40] THE LINEAR GEODETIC NUMBER OF A GRAPH
    Santhakumaran, A. P.
    Jebaraj, T.
    Chandran, S. V. Ullas
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2011, 3 (03) : 357 - 368
12345