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

M. Matamala, J. Zamora

Resultado de la investigación: Article

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

Huella dactilar

Nowhere-zero Flow
Pipe
Cycle
Even number
Cubic Graph
Induced Subgraph
Graph in graph theory
If and only if
Integer
Zero
Vertex of a graph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Citar esto

Matamala, M. ; Zamora, J. / Nowhere-Zero 5-Flows and Even (1,2)-Factors. En: Graphs and Combinatorics. 2013 ; Vol. 29, N.º 3. pp. 609-616.
@article{63a01b9a069c475e936f73d0c99ee6a2,
title = "Nowhere-Zero 5-Flows and Even (1,2)-Factors",
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 φ: 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.",
keywords = "Factors, Nowhere-zero flows",
author = "M. Matamala and J. Zamora",
year = "2013",
month = "5",
doi = "10.1007/s00373-011-1119-x",
language = "English",
volume = "29",
pages = "609--616",
journal = "Graphs and Combinatorics",
issn = "0911-0119",
publisher = "Springer Japan",
number = "3",

}

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

En: Graphs and Combinatorics, Vol. 29, N.º 3, 05.2013, p. 609-616.

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 -