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

^*Corresponding author for this work

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	131-135
Number of pages	5
Journal	Theoretical Computer Science
Volume	854
DOIs	https://doi.org/10.1016/j.tcs.2020.12.010
Publication status	Published - 2021 Jan 16

Keywords

AT-free graph
Geodetic number
Steiner number

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2020.12.010

Cite this

@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 - http://www.scopus.com/inward/record.url?scp=85097798357&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85097798357&partnerID=8YFLogxK

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this