On a local 3-Steiner convexity

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Angleški jezik
Leto izida:	2011
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK:	519.17
COBISS:	16079193
ISSN:	0195-6698
Št. ogledov:	248
Št. prenosov:	17
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	O lokalni 3-Steinerjevi konveksnosti
Sekundarni povzetek:	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.
Sekundarne ključne besede:	matematika;teorija grafov;Steinerjev interval;razdalja;dobra premostljivost;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1222-1235
Letnik:	Vol. 32
Zvezek:	no. 8
Čas izdaje:	2011
ID:	1475890