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.
Original language | English |
---|---|
Pages (from-to) | 131-135 |
Number of pages | 5 |
Journal | Theoretical Computer Science |
Volume | 854 |
DOIs | |
Publication status | Published - 2021 Jan 16 |
Keywords
- AT-free graph
- Geodetic number
- Steiner number
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science