A note on Steiner intervals and betweenness

Changat, Manoj; Lakshmikuttyamma, Anandavally K.; Mathews, Joseph; Peterin, Iztok; Narasimha-Shenoi, Prasanth G.; Tepeh, Aleksandra

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	A note on Steiner intervals and betweenness
Authors:	ID Changat, Manoj (Author) ID Lakshmikuttyamma, Anandavally K. (Author) ID Mathews, Joseph (Author) ID Peterin, Iztok (Author) ID Narasimha-Shenoi, Prasanth G. (Author) ID Tepeh, Aleksandra (Author)
Files:	http://dx.doi.org/10.1016/j.disc.2011.08.009
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
Abstract:	Geodetka in geodetski interval, ki je sestavljen iz vseh vozlišč, ki pripadajo kakšni geodetki med fiksnim parom vozlišč v povezanem grafu $G$ , sta sestavni del metrične teorije grafov. Prav tako je znano, da je Steinerjevo drevo (multi) množice s $k$ ( $k>2$ ) vozlišči, posplošitev geodetke. V (B. Brešar, M. Changat, J. Mathews, I. Peterin, P. G. Narasimha-Shenoi, A. Tepeh Horvat, Steiner intervals, geodesic intervals, and betweenness, Discrete Math. 309 (2009) 6114--6125) so se avtorji ukvarjali s $k$ -Steinerjevimi intervali $S(u_{1},u_{2},ldots, u_{k})$ povezanih grafov ( $k geq 3$ ) kot $k$ -arnimi posplošitvami geodetskih intervalov. Analogno sta bila iz binarne na $k$ -arno funkcijo posplošena tudi vmesnostni aksiom (b2) in monotoni aksiom(m) kot: za vsa vozlišča $u_{1}, ldots, u_{k}, x, x_{1}, ldots, x_{k} in V(G)$ , ki niso nujno različna $(b2)quad x in S(u_{1}, u_{2}, ldots, u_{k}) Rightarrow S(x, u_{2}, ldots, u_{k}) subseteq S(u_{1}, u_{2}, ldots, u_{k}),$ $(m) quad x_{1}, ldots, x_{k} in S(u_{1}, ldots, u_{k})Rightarrow S(x_{1}, ldots,x_{k}) subseteq S(u_{1}, ldots, u_{k}).$ Avtorji so v zgoraj omenjenem članku domnevali, da $3$ -Steinerjev interval povezanega grafa $G$ zadošča vmesnostnemu aksiomu (b2) natanko tedaj, ko je vsak blok grafa $G$ geodetski z diametrom največ 2. V tem delu dokažemo to domnevo. Pri tem dodatno dokažemo, da v vsakem geodetskem bloku z diametrom vsaj 3 obstaja izometrični cikel dolžine $2k+1$ , $k>2$ . Prav tako predstavimo dodaten aksiom (b2(2)), ki je smiseln le za 3-Steinerjeve intervale in pokažemo, da je le ta ekvivalenten monotonemu aksiomu.
Keywords:	matematika, teorija grafov, Steinerjev interval, geodetski graf, vmesnost, mathematics, graph theory, Steiner interval, geodetic graph, betweenness
Year of publishing:	2011
Number of pages:	Str. 2601-2609
Numbering:	Vol. 311, iss. 22
PID:	20.500.12556/DKUM-51908
UDC:	519.17
ISSN on article:	0012-365X
COBISS.SI-ID:	16078937
NUK URN:	URN:SI:UM:DK:SNZ0S68F
Publication date in DKUM:	10.07.2015
Views:	1032
Downloads:	87
Metadata:
Categories:	Misc.
:	CHANGAT, Manoj, LAKSHMIKUTTYAMMA, Anandavally K., MATHEWS, Joseph, PETERIN, Iztok, NARASIMHA-SHENOI, Prasanth G. and TEPEH, Aleksandra, 2011, A note on Steiner intervals and betweenness. Discrete mathematics [online]. 2011. Vol. 311, no. 22, p. 2601–2609. [Accessed 31 March 2025]. Retrieved from: http://dx.doi.org/10.1016/j.disc.2011.08.009 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:

No similar works found

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:	Discrete mathematics
Shortened title:	Discrete math.
Publisher:	North-Holland
ISSN:	0012-365X
COBISS.SI-ID:	1118479

Secondary language

Language:	English
Title:	Notica o 3-Steinerjevih intervalih in vmesnost
Abstract:	The geodesic and geodesic interval, namely the set of all vertices lying on geodesics between a pair of vertices in a connected graph, is a part of folklore in metric graph theory. It is also known that Steiner tree of a (multi) set with $k$ ( $k>2$ ) vertices, generalizes geodesics. In (B. Brešar, M. Changat, J. Mathews, I. Peterin, P. G. Narasimha-Shenoi, A. Tepeh Horvat, Steiner intervals, geodesic intervals, and betweenness, Discrete Math. 309 (2009) 6114-6125) the authors studied the $k$ -Steiner intervals $S(u_{1}, u_{2}, ldots, u_{k})$ on connected graphs ( $k geq 3$ ) asthe $k$ -ary generalization of the geodesic intervals. The analogous betweenness axiom (b2) and the monotone axiom (m) were generalized from binary to $k$ -ary functions as: for any $u_{1}, ldots, u_{k}, x, x_{1}, ldots, x_{k} in V(G)$ which are not necessarily distinct, $(b2) quad x in S(u_{1}, u_{2}, ldots, u_{k}) Rightarrow S(x,u_{2}, ldots, u_{k}) subseteq S(u_{1}, u_{2}, ldots, u_{k}),$ $$(m) quad x_{1}, ldots, x_{k} in S(u_{1}, ldots, u_{k}) Rightarrow S(x_{1}, ldots, x_{k}) subseteq S(u_{1}, ldots, u_{k}). ▫$$ The authors conjectured that the ▫$3$ -Steiner interval on a connected graph $G$ satisfies the betweenness axiom (b2) if and only if each block of $G$ is geodetic of diameter at most 2. In this paper we settle this conjecture. For this we show that there exists an isometric cycle of length $2k+1$ , $k>2$ , in every geodetic block of diameter at least 3. We also introduce another axiom (b2(2)), which is meaningful only to $3$ -Steiner intervals and show that this axiom is equivalent to the monotone axiom.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back