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

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

摘要

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.

原文英語
頁(從 - 到)131-135
頁數5
期刊Theoretical Computer Science
854
DOIs
出版狀態已發佈 - 2021 一月 16

ASJC Scopus subject areas

  • 理論電腦科學
  • 電腦科學(全部)

指紋

深入研究「A note on the geodetic number and the Steiner number of AT-free graphs」主題。共同形成了獨特的指紋。

引用此