Steiner intervals, geodesic intervals, and betweenness

Brešar, Boštjan; Changat, Manoj; Mathews, Joseph; Peterin, Iztok; Narasimha-Shenoi, Prasanth G.; Tepeh, Aleksandra

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Steiner intervals, geodesic intervals, and betweenness
Avtorji:	ID Brešar, Boštjan (Avtor) ID Changat, Manoj (Avtor) ID Mathews, Joseph (Avtor) ID Peterin, Iztok (Avtor) ID Narasimha-Shenoi, Prasanth G. (Avtor) ID Tepeh, Aleksandra (Avtor)
Datoteke:	http://dx.doi.org/10.1016/j.disc.2009.05.022
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	FNM - Fakulteta za naravoslovje in matematiko
Opis:	Koncept $k$ -Steinerjevih intervalov naravno posplošuje geodetske (binarne) intervale. Definiran je kot preslikava $S: Vtimes cdots times V longrightarrow 2^V$ , kjer je $S(u_1, dots ,u_k)$ množica tistih vozlišč grafa $G$ , ki ležijo na kakem Steinerjevem drevesu glede na multimnožico $W = {u_1, dots ,u_k}$ vozlišč iz $G$ . V tem članku za vsako naravno število $k$ dokažemo karakterizacijo razreda tistih grafov, v katerih imajo vsi $k$ -Steinerjevi intervali t.i. lastnost unije, ki pravi, da $S(u_1,ldots, u_k)$ sovpada z unijo geodetskih intervalov $I(u_i,u_j)$ med vsemi pari vozlišč iz $W$ . Izkaže se, da tedaj, ko je $k>3$ , ta razred sovpada z razredom grafov, v katerih $k$ -Steinerjev interval zadošča aksiomu monotonosti(m), kot tudi z razredom grafov, v katerih $k$ -Steinerjev interval zadošča aksiomu (b2), ki sta pogoja iz teorije vmesnosti. In sicer preslikava $S$ zadošča aksiomu (m), če iz $x_1, dots ,x_k in S(u_1, dots ,u_k)$ sledi $S(x_1, dots ,x_k) subseteq S(u_1, dots ,u_k)$ ; ter $S$ zadošča (b2), če iz $x in S(u_1,u_2, dots ,u_k)$ sledi $S(x,u_2, dots ,u_k) subseteq S(u_1, dots ,u_k)$ . V primeru $k=3$ so ti trije razredi grafov različni in za razreda grafov, v katerih Steinerjev interval zadošča lastnosti unije oz. aksiomu monotonosti (m), dokažemo strukturni karakterizaciji. Prav tako predstavimo več delnih ugotovitev za razred grafov, v katerih 3-Steinerjev interval zadošča aksimu (b2), ki vodijo do domneve, da so to natanko tisti grafi, v katerih je vsak blok geodetski graf z diametrom 2.
Ključne besede:	matematika, teorija grafov, Steinerjev interval, geodetski interval, razdalja, vmesnost, monotonost, bločni graf, mathematics, graph theory, Steiner interval, geodesic interval, distance, betweenness, monotonicity, block graph
Leto izida:	2009
Št. strani:	str. 6114-6125
Številčenje:	Vol. 309, iss. 20
PID:	20.500.12556/DKUM-51807
UDK:	519.17
COBISS.SI-ID:	15334233
ISSN pri članku:	0012-365X
NUK URN:	URN:SI:UM:DK:ZHGHZXK8
Datum objave v DKUM:	10.07.2015
Število ogledov:	1165
Število prenosov:	95
Metapodatki:
Področja:	Ostalo
:	BREŠAR, Boštjan, CHANGAT, Manoj, MATHEWS, Joseph, PETERIN, Iztok, NARASIMHA-SHENOI, Prasanth G. in TEPEH, Aleksandra, 2009, Steiner intervals, geodesic intervals, and betweenness. Discrete mathematics [na spletu]. 2009. Vol. 309, no. 20, p. 6114–6125. [Dostopano 1 april 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.disc.2009.05.022 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Podobna dela iz repozitorija:

Podobna dela iz ostalih repozitorijev:

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:	Discrete mathematics
Skrajšan naslov:	Discrete math.
Založnik:	North-Holland
ISSN:	0012-365X
COBISS.SI-ID:	1118479

Sekundarni jezik

Jezik:	Neznan jezik
Naslov:	Steinerjevi intervali, geodetski intervali in vmesnost
Opis:	The concept of the $k$ -Steiner interval is a natural generalization of the geodesic (binary) interval. It is defined as a mapping $S: V times cdots times V longrightarrow 2^V$ such that $S(u_1,...,u_k)$ consists of all vertices in $G$ that lie on some Steiner tree with respect to a multiset $W ={u_1,...,u_k}$ of vertices from $G$ . In this paper we obtain, for each $k$ , a characterization of the class of graphs in which every $k$ -Steiner interval $S$ has the so-called union property, which says that $S(u_1,...,u_k)$ coincides with the union of geodesic intervals $I(u_i,u_j)$ between all pairs from $W$ . It turns out that, as soon as $k>3$ , this class coincides with the class of graphs in which the $k$ -Steiner interval enjoys the monotone axiom (m), respectively (b2) axiom, the conditions from betweenness theory. Notably, $S$ satisfies (m), if $x_1,...,x_k in S(u_1,...,u_k)$ implies $S(x_1,...,x_k) subseteq S(u_1,...,u_k)$ , and $S$ satisfies (b2) if $x in S(u_1,u_2,...,u_k)$ implies $S(x,u_2,...,u_k) subseteq S(u_1,...,u_k)$ . In the case $k=3$ , these three classes are different, and we give structural characterizations of graphs for which their Steiner interval $S$ satisfies the union property as well as the monotone axiom (m). We also prove several partial observations on the class ofgraphs in which the 3-Steiner interval satisfies (b2), which lead to the conjecture that these are precisely the graphs in which every block is a geodetic graph with diameter at most two.

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj