Nowhere-Zero 5-Flows and Even (1,2)-Factors |
| |
Authors: | M Matamala J Zamora |
| |
Institution: | 1. Departamento de Ingeniería Matemática y Centro de Modelamiento Matemático (UMI 2807, CNRS), Universidad de Chile, Santiago, Chile 2. Departamento de Matemáticas, Universidad Andres Bello, Santiago, Chile
|
| |
Abstract: | A graph G = (V, E) admits a nowhere-zero k-flow if there exists an orientation H = (V, A) of G and an integer flow ${\varphi:A \to \mathbb{Z}}$ such that for all ${a \in A, 0 < |\varphi(a)| < k}$ . Tutte conjectured that every bridgeless graphs admits a nowhere-zero 5-flow. A (1,2)-factor of G is a set ${F \subseteq E}$ such that the degree of any vertex v in the subgraph induced by F is 1 or 2. Let us call an edge of G, F-balanced if either it belongs to F or both its ends have the same degree in F. Call a cycle of G F-even if it has an even number of F-balanced edges. A (1,2)-factor F of G is even if each cycle of G is F-even. The main result of the paper is that a cubic graph G admits a nowhere-zero 5-flow if and only if G has an even (1,2)-factor. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|