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

Wing Kai Hon, Ton Kloks, Hsiang Hsuan Liu, Hung Lung Wang*, Yue Li Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)131-135
Number of pages5
JournalTheoretical Computer Science
Volume854
DOIs
Publication statusPublished - 2021 Jan 16

Keywords

  • AT-free graph
  • Geodetic number
  • Steiner number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'A note on the geodetic number and the Steiner number of AT-free graphs'. Together they form a unique fingerprint.

Cite this