On a local 3-Steiner convexity

被引:4
作者
Bresar, Bostjan [1 ,2 ]
Gologranc, Tanja [2 ]
机构
[1] Univ Maribor, Fac Nat Sci & Math, Maribor, Slovenia
[2] Inst Math Phys & Mech, Ljubljana, Slovenia
关键词
STEINER INTERVALS; GRAPHS;
D O I
10.1016/j.ejc.2011.06.001
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given a graph G and a set of vertices W subset of 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 subset of V(G) is called g(3)-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 g(3)-convex in a graph G, then G has no induced house nor twin C(4), 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 g(3)-convex. (C) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码:1222 / 1235
页数:14
相关论文
共 8 条
[1]   Steiner intervals, geodesic intervals, and betweenness [J].
Bresar, Bostjan ;
Changat, Manoj ;
Mathews, Joseph ;
Peterin, Iztok ;
Narasimha-Shenoi, Prasanth G. ;
Horvat, Aleksandra Tepeh .
DISCRETE MATHEMATICS, 2009, 309 (20) :6114-6125
[2]   On 3-Steiner simplicial orderings [J].
Caceres, Jose ;
Oellermann, Ortrud R. .
DISCRETE MATHEMATICS, 2009, 309 (19) :5828-5833
[3]   Convexities related to path properties on graphs [J].
Changat, M ;
Mulder, HM ;
Sierksma, G .
DISCRETE MATHEMATICS, 2005, 290 (2-3) :117-131
[4]   ON LOCAL CONVEXITY IN GRAPHS [J].
FARBER, M ;
JAMISON, RE .
DISCRETE MATHEMATICS, 1987, 66 (03) :231-247
[5]   Local Steiner convexity [J].
Henning, Michael A. ;
Nielsen, Morten H. ;
Ciellermann, Ortrud R. .
EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (05) :1186-1193
[6]   Steiner intervals in graphs [J].
Kubicka, E ;
Kubicki, G ;
Oellermann, OR .
DISCRETE APPLIED MATHEMATICS, 1998, 81 (1-3) :181-190
[7]   Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs [J].
Oellermann, Ortrud R. ;
Puertas, Maria Luz .
DISCRETE MATHEMATICS, 2007, 307 (01) :88-96
[8]  
van de Vel M.L.J., 1993, Theory of Convex Structures