### Resumen

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 φ: A → ℤ such that for all a ∈ A, 0 < {pipe}φ(a){pipe} < K. Tutte conjectured that every bridgeless graphs admits a nowhere-zero 5-flow. A (1,2)-factor of G is a set F ⊆ 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 GF-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.

Idioma original | English |
---|---|

Páginas (desde-hasta) | 609-616 |

Número de páginas | 8 |

Publicación | Graphs and Combinatorics |

Volumen | 29 |

N.º | 3 |

DOI | |

Estado | Published - may 2013 |

### Huella dactilar

### ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Theoretical Computer Science

### Citar esto

*Graphs and Combinatorics*,

*29*(3), 609-616. https://doi.org/10.1007/s00373-011-1119-x

}

*Graphs and Combinatorics*, vol. 29, n.º 3, pp. 609-616. https://doi.org/10.1007/s00373-011-1119-x

**Nowhere-Zero 5-Flows and Even (1,2)-Factors.** / Matamala, M.; Zamora, J.

Resultado de la investigación: Article

TY - JOUR

T1 - Nowhere-Zero 5-Flows and Even (1,2)-Factors

AU - Matamala, M.

AU - Zamora, J.

PY - 2013/5

Y1 - 2013/5

N2 - 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 φ: A → ℤ such that for all a ∈ A, 0 < {pipe}φ(a){pipe} < K. Tutte conjectured that every bridgeless graphs admits a nowhere-zero 5-flow. A (1,2)-factor of G is a set F ⊆ 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 GF-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.

AB - 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 φ: A → ℤ such that for all a ∈ A, 0 < {pipe}φ(a){pipe} < K. Tutte conjectured that every bridgeless graphs admits a nowhere-zero 5-flow. A (1,2)-factor of G is a set F ⊆ 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 GF-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.

KW - Factors

KW - Nowhere-zero flows

UR - http://www.scopus.com/inward/record.url?scp=84877602832&partnerID=8YFLogxK

U2 - 10.1007/s00373-011-1119-x

DO - 10.1007/s00373-011-1119-x

M3 - Article

AN - SCOPUS:84877602832

VL - 29

SP - 609

EP - 616

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

IS - 3

ER -