Nowhere-zero 3-flows in squares of graphs
type: Item
instance of: scholarly article
title: Nowhere-zero 3-flows in squares of graphs
zbMATH Open document ID: 1018.05031
author: Rui Xu
author: Cun-Quan Zhang
published in: The Electronic Journal of Combinatorics
publication date: 2003-05-13T00:00:00Z
full work available at URL: https://eudml.org/doc/122804
full work available at URL: v10i1r5.html
review text: Let \(D\) be an orientation (of the edges) of a graph \(G\) and \(f: E(G) \rightarrow \mathbb{Z}\) be a function. \((D, f)\) is called a \(k\)-flow of \(G\) if \(|f(e)|\leq k-1\) for every edge \(e\in E(G)\) and \[ \sum_{e\in E^+(v)} f(e) = \sum_{e\in E^-(v)} f(e) \] for every \(v\in V(G)\), where \(E^+(v)\) (\(E^-(v)\)) denotes the set of all edges with tails (heads) at \(v\). A \(k\)-flow \((D, f)\) is nowhere-zero if \(f(e)\not= 0\) for every edge \(e\) of \(G\). Tutte's \(3\)-flow conjecture states that every \(4\)-edge-connected graph admits a nowhere-zero \(3\)-flow. The square \(G^2\) of a graph \(G\) is obtained from \(G\) by adding all edges joing distance \(2\) vertices in \(G\). The authors characterize all squares \(G^2\) admitting a nowhere-zero \(3\)-flow. It follows from their characterization that if the minimum vertex degree of \(G^2\) is at least \(4\) then \(G^2\) admits a nowhere-zero \(3\)-flow. This confirms Tutte's conjecture for squares of graphs.
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 90B10
zbMATH DE Number: 1862497
zbMATH Keywords: nowhere-zero flow
zbMATH Keywords: squares of graphs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1862497