Name
Abstract | ||
|---|---|---|
The odd-edge-connectivity of a graph G is the size of the smallest odd edge cut of G. Tutte conjectured that every odd-5-edge-connected graph admits a nowhere-zero 3-flow. As a weak version of this famous conjecture, Jaeger conjectured that there is an integer k such that every k-edge-connected graph admits a nowhere-zero 3-flow. Jaeger [F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B 26 (1979) 205-216] proved that every 4-edge-connected graph admits a nowhere-zero 4-flow. Galluccio and Goddyn [A. Galluccio, L.A. Goddyn, The circular flow number of a 6-edge-connected graph is less than four, Combinatorica 22 (2002) 455-459] proved that the flow index of every 6-edge-connected graph is strictly less than 4. This result is further strengthened in this paper that the flow index of every odd-7-edge-connected graph is strictly less than 4. The second main result in this paper solves an open problem that every odd-(2k+1)-edge-connected graph contains k edge-disjoint parity subgraphs. The third main theorem of this paper proves that if the odd-edge-connectivity of a graph G is at least4@?log"2|V(G)|@?+1, then G admits a nowhere-zero 3-flow. This result is a partial result to the weak 3-flow conjecture by Jaeger and improves an earlier result by Lai et al. The fourth main result of this paper proves that every odd-(4t+1)-edge-connected graph G has a circular(2t+1)even subgraph double cover. This result generalizes an earlier result of Jaeger. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.jctb.2012.03.002 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
main result,odd-5-edge-connected graph,k-edge-connected graph,4-edge-connected graph,edge-connected graph,nowhere-zero 3-flow,6-edge-connected graph,large odd-edge-connectivity,graph g,parity subgraphs,odd-7-edge-connected graph,earlier result | Discrete mathematics,Combinatorics,Graph power,Graph factorization,Cubic graph,Factor-critical graph,Petersen graph,Graph minor,Universal graph,Voltage graph,Mathematics | Journal |
Volume | Issue | ISSN |
102 | 4 | 0095-8956 |
Citations | PageRank | References |
1 | 0.38 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jinlong Shu | 1 | 99 | 24.28 |
| Cun-Quan Zhang | 2 | 496 | 69.81 |
| Taoye Zhang | 3 | 19 | 3.73 |