Convexities in Some Special Graph Classes ---New Results in AT-free Graphs and Beyond

Wing-Kai Hon; Ton Kloks; Hsiang-Hsuan Liu; Hung-Lung Wang; Yue-Li Wang

paper

Convexities in Some Special Graph Classes ---New Results in AT-free Graphs and Beyond

arXiv:1509.04944

Abstract

We study convexity properties of graphs. In this paper we present a linear-time algorithm for the geodetic number in tree-cographs. Settling a 10-year-old conjecture, we prove that the Steiner number is at least the geodetic number in AT-free graphs. Computing a maximal and proper monophonic set in $\AT$-free graphs is NP-complete. We present polynomial algorithms for the monophonic number in permutation graphs and the geodetic number in $P_{4}$ - sparse graphs.

arXiv comment20 pages