Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s00373-011-1119-x | Graphs and Combinatorics |
Keywords | Field | DocType |
nowhere-zero flow factor,spanning tree,cubic graph | Discrete mathematics,Combinatorics,Line graph,Gray graph,Cubic graph,Cycle graph,Distance-hereditary graph,Symmetric graph,Universal graph,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
29 | 3 | Electronic Notes in Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martín Matamala | 1 | 158 | 21.63 |
| José Zamora | 2 | 7 | 5.95 |