NZ-flows in strong products of graphs

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

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	NZ-flows in strong products of graphs
Authors:	ID Imrich, Wilfried (Author) ID Peterin, Iztok (Author) ID Špacapan, Simon (Author) ID Zhang, Cun-Quan (Author)
Files:	http://dx.doi.org/10.1002/jgt.20455
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
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 $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.
Keywords:	matematika, teorija grafov, celoštevilski pretoki, krepki produkt, poti, cikli, nikjer ničelni pretok, mathematics, graph theory, integer flows, strong product, paths, cycles
Year of publishing:	2010
Number of pages:	str. 267-276
Numbering:	Vol. 64, iss. 4
PID:	20.500.12556/DKUM-51864
UDC:	519.17
ISSN on article:	0364-9024
COBISS.SI-ID:	15616089
NUK URN:	URN:SI:UM:DK:AIHBFNKY
Publication date in DKUM:	10.07.2015
Views:	1067
Downloads:	125
Metadata:
Categories:	Misc.
:	IMRICH, Wilfried, PETERIN, Iztok, ŠPACAPAN, Simon and ZHANG, Cun-Quan, 2010, NZ-flows in strong products of graphs. Journal of graph theory [online]. 2010. Vol. 64, no. 4, p. 267–276. [Accessed 28 April 2025]. Retrieved from: http://dx.doi.org/10.1002/jgt.20455 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Hypodontia prevalence and pattern in women with epithelial ovarian cancer

Similar works from other repositories:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	Journal of graph theory
Shortened title:	J. graph theory
Publisher:	J. Wiley & Sons
ISSN:	0364-9024
COBISS.SI-ID:	25747712

Secondary language

Language:	Unknown
Title:	NZ-pretoki v krepkem produktu grafov
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.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back