NZ-flows in strong products of graphs

Wilfried Imrich (Avtor), Iztok Peterin (Avtor), Simon Špacapan (Avtor), Cun-Quan Zhang (Avtor)

Povzetek

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 ▫$T\boxtimes 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;

Podatki

Jezik:	Angleški jezik
Leto izida:	2010
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FS - Fakulteta za strojništvo
UDK:	519.17
COBISS:	15616089
ISSN:	0364-9024
Št. ogledov:	282
Št. prenosov:	28
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	NZ-pretoki v krepkem produktu grafov
Sekundarni povzetek:	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.
Sekundarne ključne besede:	matematika;teorija grafov;celoštevilski pretoki;krepki produkt;poti;cikli;nikjer ničelni pretok;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 267-276
Letnik:	Vol. 64
Zvezek:	iss. 4
Čas izdaje:	2010
ID:	1475137