Local Steiner convexity

Michael A. Henning, Morten H. Nielsen, Ortrud R. Oellermann

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


Let G be a connected graph and let S be a set of vertices in G. The Steiner distance d (S) of S is the minimum size of a subtree of G containing S. Such a subtree of size d (S) is a Steiner tree for S. The set S is g-convex if it contains the set of all vertices that lie on some shortest u-v path in G for every pair u and v of vertices in S. The set S is k-Steiner convex, denoted by gk-convex, if for every k-element subset R of S, every vertex that belongs to some Steiner tree for R is also in S. Thus, S is g2-convex if and only if it is g-convex. In this paper, we distinguish three local convexity notions for g3-convexity and we characterize the graphs for which two of these conditions hold. For the third condition we determine some necessary conditions and some sufficient conditions for the graph class satisfying this condition.

Original languageEnglish
Pages (from-to)1186-1193
Number of pages8
JournalEuropean Journal of Combinatorics
Issue number5
Publication statusPublished - Jul 2009
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Local Steiner convexity'. Together they form a unique fingerprint.

Cite this