| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:NZ-flows in strong products of graphs
Avtorji:Imrich, Wilfried (Avtor)
Peterin, Iztok (Avtor)
Špacapan, Simon (Avtor)
Zhang, Cun-Quan (Avtor)
Datoteke:URL http://dx.doi.org/10.1002/jgt.20455
 
Jezik:Angleški jezik
Vrsta gradiva:Delo ni kategorizirano (r6)
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Opis:Za krepki produkt ▫$G_1 boxtimes G_2$▫ grafov ▫$G_1$▫ in ▫$G_2$▫ dokažemo, da je ▫${mathbb{Z}}_3$▫-pretočno kontraktibilen natanko tedaj, ko ▫$G_1 boxtimes G_2$▫ ni izomorfen ▫$Tboxtimes K_2$▫ (kar poimenujemo ▫$K_4$▫-drevo), kjer je ▫$T$▫ drevo. Sledi, da za ▫$G_1 boxtimes G_2$▫ obstaja NZ 3-pretok, razen če je ▫$G_1 boxtimes G_2$▫ ▫$K_4$▫-drevo. Dokaz je konstruktiven in implicira polinomski algoritem, ki nam vrne NZ 3-pretok, če ▫$G_1 boxtimes G_2$▫ ni ▫$K_4$▫-drevo, oziroma NZ 4-pretok sicer.
Ključne besede:matematika, teorija grafov, celoštevilski pretoki, krepki produkt, poti, cikli, nikjer ničelni pretok, mathematics, graph theory, integer flows, strong product, paths, cycles
Leto izida:2010
Št. strani:str. 267-276
Številčenje:Vol. 64, iss. 4
UDK:519.17
COBISS_ID:15616089 Novo okno
ISSN pri članku:0364-9024
NUK URN:URN:SI:UM:DK:AIHBFNKY
Število ogledov:538
Število prenosov:100
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:Journal of graph theory
Skrajšan naslov:J. graph theory
Založnik:J. Wiley & Sons
ISSN:0364-9024
COBISS.SI-ID:25747712 Novo okno

Sekundarni jezik

Jezik:Neznan jezik
Naslov:NZ-pretoki v krepkem produktu grafov
Opis:We prove that the strong product ▫$G_1 boxtimes G_2$▫ of ▫$G_1$▫ and ▫$G_2$▫ is ▫${mathbb Z}_3$▫-flow contractible if and only if ▫$G_1 boxtimes G_2$▫ is not ▫$T boxtimes K_2$▫, where ▫$T$▫ is a tree (we call ▫$T boxtimes K_2$▫ a ▫$K_4$▫-tree). It follows that ▫$G_1 boxtimes G_2$▫ admits an NZ 3-flow unless ▫$G_1 boxtimes G_2$▫ is a ▫$K_4$▫-tree. We also give a constructive proof that yields a polynomial algorithm whose output is an NZ 3-flow if ▫$G_1 boxtimes G_2$▫ is not a ▫$K_4$▫-tree, and an NZ 4-flow otherwise.


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