NZ-flows in strong products of graphs

Imrich, Wilfried; Peterin, Iztok; Špacapan, Simon; Zhang, Cun-Quan

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	NZ-flows in strong products of graphs
Avtorji:	ID Imrich, Wilfried (Avtor) ID Peterin, Iztok (Avtor) ID Špacapan, Simon (Avtor) ID Zhang, Cun-Quan (Avtor)
Datoteke:	http://dx.doi.org/10.1002/jgt.20455
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
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
PID:	20.500.12556/DKUM-51864
UDK:	519.17
COBISS.SI-ID:	15616089
ISSN pri članku:	0364-9024
NUK URN:	URN:SI:UM:DK:AIHBFNKY
Datum objave v DKUM:	10.07.2015
Število ogledov:	1067
Število prenosov:	125
Metapodatki:
Področja:	Ostalo
:	IMRICH, Wilfried, PETERIN, Iztok, ŠPACAPAN, Simon in ZHANG, Cun-Quan, 2010, NZ-flows in strong products of graphs. Journal of graph theory [na spletu]. 2010. Vol. 64, no. 4, p. 267–276. [Dostopano 15 april 2025]. Pridobljeno s: http://dx.doi.org/10.1002/jgt.20455 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:	Journal of graph theory
Skrajšan naslov:	J. graph theory
Založnik:	J. Wiley & Sons
ISSN:	0364-9024
COBISS.SI-ID:	25747712

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