Log In

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

Files

1_s2.0_S030439752030712X_main.pdf (243.82 KB)

Publication date

2021-01-16

Authors

Hon, Wing-Kai
Kloks, Ton
Liu, AlisonISNI 0000000492910289
Wang, Hung-Lung
Wang, Yue-Li

Editors

Advisors

Supervisors

DOI

https://doi.org/10.1016/j.tcs.2020.12.010

Document Type

Article

Metadata

Show full item record

Collections

Utrecht University Repository
Open Access logo

License

taverne

Abstract

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.

Keywords

AT-free graph, Geodetic number, Steiner number, Taverne

Citation

Hon, W-K, Kloks, T, Liu, H-H, Wang, H-L & Wang, Y-L 2021, 'A note on the geodetic number and the Steiner number of AT-free graphs', Theoretical Computer Science, vol. 854, pp. 131-135. https://doi.org/10.1016/j.tcs.2020.12.010

URI

http://hdl.handle.net/1874/416347