On a local 3-Steiner convexity

Brešar, Boštjan; Dravec, Tanja

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	On a local 3-Steiner convexity
Authors:	ID Brešar, Boštjan (Author) ID Dravec, Tanja (Author)
Files:	http://dx.doi.org/10.1016/j.ejc.2011.06.001
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
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
Year of publishing:	2011
Number of pages:	str. 1222-1235
Numbering:	Vol. 32, no. 8
PID:	20.500.12556/DKUM-51909
UDC:	519.17
ISSN on article:	0195-6698
COBISS.SI-ID:	16079193
NUK URN:	URN:SI:UM:DK:JORLTX3K
Publication date in DKUM:	10.07.2015
Views:	1062
Downloads:	50
Metadata:
Categories:	Misc.
:	BREŠAR, Boštjan and DRAVEC, Tanja, 2011, On a local 3-Steiner convexity. European journal of combinatorics [online]. 2011. Vol. 32, no. 8, p. 1222–1235. [Accessed 5 April 2025]. Retrieved from: http://dx.doi.org/10.1016/j.ejc.2011.06.001 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Similar works from other repositories:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	European journal of combinatorics
Shortened title:	Eur. j. comb.
Publisher:	Academic Press
ISSN:	0195-6698
COBISS.SI-ID:	25427968

Secondary language

Language:	English
Title:	O lokalni 3-Steinerjevi konveksnosti
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.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back