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

doi:10.1016/j.tcs.2020.12.010

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	https://doi.org/10.1016/j.tcs.2020.12.010
出版狀態	已發佈 - 2021 1月 16

ASJC Scopus subject areas

理論電腦科學
一般電腦科學

存取文件

10.1016/j.tcs.2020.12.010

其它文件與鏈接

引用此

@article{f47a8afd97104a2d9e247d9ad3a89b33,

title = "A note on the geodetic number and the Steiner number of AT-free graphs",

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",

author = "Hon, \{Wing Kai\} and Ton Kloks and Liu, \{Hsiang Hsuan\} and Wang, \{Hung Lung\} and Wang, \{Yue Li\}",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2021",

month = jan,

day = "16",

doi = "10.1016/j.tcs.2020.12.010",

language = "English",

volume = "854",

pages = "131--135",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier BV",

}

TY - JOUR

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

AU - Hon, Wing Kai

AU - Kloks, Ton

AU - Liu, Hsiang Hsuan

AU - Wang, Hung Lung

AU - Wang, Yue Li

PY - 2021/1/16

Y1 - 2021/1/16

N2 - 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.

AB - 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.

KW - AT-free graph

KW - Geodetic number

KW - Steiner number

UR - https://www.scopus.com/pages/publications/85097798357

UR - https://www.scopus.com/pages/publications/85097798357#tab=citedBy

U2 - 10.1016/j.tcs.2020.12.010

DO - 10.1016/j.tcs.2020.12.010

M3 - Article

AN - SCOPUS:85097798357

SN - 0304-3975

VL - 854

SP - 131

EP - 135

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

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

摘要

ASJC Scopus subject areas

存取文件

其它文件與鏈接

指紋

引用此