NZ-flows in strong products of graphs

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

Abstract

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.

Keywords

matematika;teorija grafov;celoštevilski pretoki;krepki produkt;poti;cikli;nikjer ničelni pretok;mathematics;graph theory;integer flows;strong product;paths;cycles;

Data

Language:	English
Year of publishing:	2010
Typology:	1.01 - Original Scientific Article
Organization:	UM FS - Faculty of Mechanical Engineering
UDC:	519.17
COBISS:	15616089
ISSN:	0364-9024
Views:	282
Downloads:	28
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	NZ-pretoki v krepkem produktu grafov
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;celoštevilski pretoki;krepki produkt;poti;cikli;nikjer ničelni pretok;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 267-276
Volume:	Vol. 64
Issue:	iss. 4
Chronology:	2010
ID:	1475137