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

M. Matamala, J. Zamora

Resultado de la investigación: Contribución a una revistaArtículo

1 Cita (Scopus)

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 originalInglés
Páginas (desde-hasta)609-616
Número de páginas8
PublicaciónGraphs and Combinatorics
Volumen29
N.º3
DOI
EstadoPublicada - may 2013

Áreas temáticas de ASJC Scopus

  • Matemáticas discretas y combinatorias
  • Ciencia computacional teórica

Huella Profundice en los temas de investigación de 'Nowhere-Zero 5-Flows and Even (1,2)-Factors'. En conjunto forman una huella única.

  • Citar esto