On a local 3-Steiner convexity

Boštjan Brešar (Author), Tanja Gologranc (Author)

Abstract

Za dani graf ▫$G$▫ je Steinerjev interval množice vozlišč ▫$W \subset V(G)$▫ množica tistih vozlišč, ki ležijo na kakem Steinerjevem drevesu glede na ▫$W$▫. Množica ▫$U \subset V(G)$▫ je ▫$g_3$▫-konveksna v ▫$G$▫, če Steinerjev interval poljubne trojice vozlišč iz ▫$U$▫ v celoti leži v ▫$U$▫. Henning, Nielsen in Oellermann (2009) so dokazali, da graf ▫$G$▫, v katerem so ▫$j$▫-krogle ▫$g_3$▫-konveksne za vsak ▫$j \ge 1$▫, ne vsebuje hiše niti grafov dvojčkov ▫$C_4$▫ kot induciranih podgrafov in vsak cikel v ▫$G$▫ dolžine vsaj šest je dobro premostljiv. V tem članku dokažemo, da velja tudi obrat tega izreka, s čimer okarakteriziramo grafe z ▫$g_3$▫-konveksnimi kroglami.

Keywords

matematika;teorija grafov;Steinerjev interval;razdalja;dobra premostljivost;mathematics;graph theory;Steiner interval;distance;well-bridgeness;

Data

Language:	English
Year of publishing:	2011
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
UDC:	519.17
COBISS:	16079193
ISSN:	0195-6698
Views:	248
Downloads:	17
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	O lokalni 3-Steinerjevi konveksnosti
Secondary abstract:	Given a graph ▫$G$▫ and a set of vertices ▫$W \subset V(G)$▫, the Steiner interval of ▫$W$▫ is the set of vertices that lie on some Steiner tree with respect to ▫$W$▫. A set ▫$W \subset 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) proved that if every ▫$j$▫-ball for all ▫$j \ge 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.
Secondary keywords:	matematika;teorija grafov;Steinerjev interval;razdalja;dobra premostljivost;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1222-1235
Volume:	Vol. 32
Issue:	no. 8
Chronology:	2011
ID:	1475890