| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:Steiner intervals, geodesic intervals, and betweenness
Avtorji:Brešar, Boštjan (Avtor)
Changat, Manoj (Avtor)
Mathews, Joseph (Avtor)
Peterin, Iztok (Avtor)
Narasimha-Shenoi, Prasanth G. (Avtor)
Tepeh, Aleksandra (Avtor)
Datoteke:URL http://dx.doi.org/10.1016/j.disc.2009.05.022
 
Jezik:Angleški jezik
Vrsta gradiva:Delo ni kategorizirano (r6)
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
UDK:519.17
COBISS_ID:15334233 Povezava se odpre v novem oknu
ISSN pri članku:0012-365X
NUK URN:URN:SI:UM:DK:ZHGHZXK8
Število ogledov:326
Število prenosov:48
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:Ostalo
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

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 Novo okno

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
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici