Loading…
On a local 3-Steiner convexity
Given a graph G and a set of vertices W⊂V(G), the Steiner interval of W is the set of vertices that lie on some Steiner tree with respect to W. A set U⊂V(G) is called g3-convex in G, if the Steiner interval with respect to any three vertices from U lies entirely in U. Henning et al. (2009) [5] prove...
Saved in:
Published in: | European journal of combinatorics 2011-11, Vol.32 (8), p.1222-1235 |
---|---|
Main Authors: | , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | Given a graph G and a set of vertices W⊂V(G), the Steiner interval of W is the set of vertices that lie on some Steiner tree with respect to W. A set U⊂V(G) is called g3-convex in G, if the Steiner interval with respect to any three vertices from U lies entirely in U. Henning et al. (2009) [5] proved that if every j-ball for all j≥1 is g3-convex in a graph G, then G has no induced house nor twin C4, and every cycle in G of length at least six is well-bridged. In this paper we show that the converse of this theorem is true, thus characterizing the graphs in which all balls are g3-convex. |
---|---|
ISSN: | 0195-6698 1095-9971 |
DOI: | 10.1016/j.ejc.2011.06.001 |