共查询到20条相似文献,搜索用时 31 毫秒
1.
It was conjectured by A. Bouchet that every bidirected graph which admits a nowhere-zero k-flow admits a nowhere-zero 6-flow. He proved that the conjecture is true when 6 is replaced by 216. O. Zyka improved the
result with 6 replaced by 30. R. Xu and C. Q. Zhang showed that the conjecture is true for 6-edge-connected graph, which is
further improved by A. Raspaud and X. Zhu for 4-edge-connected graphs. The main result of this paper improves Zyka’s theorem
by showing the existence of a nowhere-zero 25-flow for all 3-edge-connected graphs. 相似文献
2.
It was conjectured by Bouchet that every bidirected graph which admits a nowhere-zero κ flow will admit a nowhere-zero 6-flow. He proved that the conjecture is true when 6 is replaced by 216. Zyka improved the result with 6 replaced by 30. Xu and Zhang showed that the conjecture is true for 6-edge-connected graphs. And for 4-edge-connected graphs, Raspaud and Zhu proved it is true with 6 replaced by 4. In this paper, we show that Bouchet's conjecture is true with 6 replaced by 15 for 3-edge-connected graphs. 相似文献
3.
In 1983, Bouchet conjectured that every flow-admissible signed graph admits a nowhere-zero 6-flow. By Seymour's 6-flow theorem, Bouchet's conjecture holds for signed graphs with all edges positive. Recently, Rollová et al proved that every flow-admissible signed cubic graph with two negative edges admits a nowhere-zero 7-flow, and admits a nowhere-zero 6-flow if its underlying graph either contains a bridge, or is 3-edge-colorable, or is critical. In this paper, we improve and extend these results, and confirm Bouchet's conjecture for signed graphs with frustration number at most two, where the frustration number of a signed graph is the smallest number of vertices whose deletion leaves a balanced signed graph. 相似文献
4.
Tutte’s -flow conjecture states that every -edge-connected graph admits a nowhere-zero -flow. In this paper, we characterize all graphs with independence number at most that admit a nowhere-zero -flow. The characterization of -flow verifies Tutte’s -flow conjecture for graphs with independence number at most and with order at least . In addition, we prove that every odd--edge-connected graph with independence number at most admits a nowhere-zero -flow. To obtain these results, we introduce a new reduction method to handle odd wheels. 相似文献
5.
A nowhere-zero k-flow is an assignment of edge directions and integer weights in the range 1,…, k ? 1 to the edges of an undirected graph such that at every vertex the flow in is equal to the flow out. Tutte has conjectured that every bridgeless graph has a nowhere-zero 5-flow. We show that a counterexample to this conjecture, minimal in the class of graphs embedded in a surface of fixed genus, has no face-boundary of length <7. Moreover, in order to prove or disprove Tutte's conjecture for graphs of fixed genus γ, one has to check graphs of order at most 28(γ ? 1) in the orientable case and 14(γ ? 2) in the nonorientable case. So, in particular, it follows immediately that every bridgeless graph of orientable genus ?1 or nonorientable genus ?2 has a nowhere-zero 5-flow. Using a computer, we checked that all graphs of orientable genus ?2 or nonorientable genus ?4 have a nowhere-zero 5-flow. 相似文献
6.
László Miklós Lovász Carsten Thomassen Yezhou Wu Cun-Quan Zhang 《Journal of Combinatorial Theory, Series B》2013
The main theorem of this paper provides partial results on some major open problems in graph theory, such as Tutte?s 3-flow conjecture (from the 1970s) that every 4-edge connected graph admits a nowhere-zero 3-flow, the conjecture of Jaeger, Linial, Payan and Tarsi (1992) that every 5-edge-connected graph is Z3-connected, Jaeger?s circular flow conjecture (1984) that for every odd natural number k?3, every (2k−2)-edge-connected graph has a modulo k -orientation, etc. It was proved recently by Thomassen that, for every odd number k?3, every (2k2+k)-edge-connected graph G has a modulo k-orientation; and every 8-edge-connected graph G is Z3-connected and admits therefore a nowhere-zero 3-flow. In the present paper, Thomassen?s method is refined to prove the following: For every odd number k?3, every (3k−3)-edge-connected graph has a modulo k-orientation. As a special case of the main result, every 6-edge-connected graph is Z3-connected and admits therefore a nowhere-zero 3-flow. Note that it was proved by Kochol (2001) that it suffices to prove the 3-flow conjecture for 5-edge-connected graphs. 相似文献
7.
Tutte introduced the theory of nowhere zero flows and showed that a plane graph G has a face k-coloring if and only if G has a nowhere zero A-flow, for any Abelian group A with |A|≥k. In 1992, Jaeger et al. [9] extended nowhere zero flows to group connectivity of graphs: given an orientation D of a graph G, if for any b:V(G)?A with ∑v∈V(G)b(v)=0, there always exists a map f:E(G)?A−{0}, such that at each v∈V(G), in A, then G is A-connected. Let Z3 denote the cyclic group of order 3. In [9], Jaeger et al. (1992) conjectured that every 5-edge-connected graph is Z3-connected. In this paper, we proved the following.
(i)
Every 5-edge-connected graph is Z3-connected if and only if every 5-edge-connected line graph is Z3-connected. (ii)
Every 6-edge-connected triangular line graph is Z3-connected. (iii)
Every 7-edge-connected triangular claw-free graph is Z3-connected.
8.
Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs. 相似文献
9.
Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group
Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we show that this conjecture is true for Cayley graph on generalized dihedral groups and generalized quaternion groups, which generalizes the result of F. Yang and X. Li [Inform. Process. Lett., 2011, 111: 416–419]. We also generalizes an early result of M. Nánásiová and M. ?koviera [J. Algebraic Combin., 2009, 30: 103–110]. 相似文献
10.
《Journal of Combinatorial Theory, Series B》1987,43(1):95-115
General results on nowhere-zero integral chain groups are proved and then specialized to the case of flows in bidirected graphs. For instance, it is proved that every 4-connected (resp. 3-connected and balanced triangle free) bidirected graph which has at least an unbalanced circuit and a nowhere-zero flow can be provided with a nowhere-zero integral flow with absolute values less than 18 (resp. 30). This improves, for these classes of graphs, Bouchet's 216-flow theorem (J. Combin. Theory Ser. B 34 (1982), 279–292). We also approach his 6-flow conjecture by proving it for a class of 3-connected graphs. Our method is inspired by Seymour's proof of the 6-flow theorem (J. Combin. Theory Ser. B 30 (1981), 130–136), and makes use of new connectedness properties of signed graphs. 相似文献
11.
A graph $G$ is $k$-triangular if each of its edge is contained in at least $k$ triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph $G$ is a sequence of distinct triangles $T_1 T_2\cdots T_k$ in $G$ such that for $1\leq i\leq k-1, |E(T_i )\cap E(T_{i+1})|=1$ and
$E(T_i)\cap E(T_j)=\emptyset$ if $j>i+1$. Two edges $e,e''\in E(G)$ are triangularly connected if there is a triangle-path $T_1,T_2,\cdots, T_k$ in $G$ such that $e\in E(T_1)$ and $e''\in E(T_k)$. Two edges $e,e''\in E(G)$ are equivalent if they are the same, parallel or triangularly connected. It is easy to see that this is an equivalent relation. Each equivalent class is called a triangularly connected component. In this paper, we prove that every 4-edge-connected triangular graph $G$ is ${\mathbb Z}_3$-connected, unless it has a triangularly connected component which is not ${\mathbb Z}_3$-connected but admits a nowhere-zero 3-flow. 相似文献
12.
Richard Steinberg 《Journal of Graph Theory》1984,8(2):277-285
Heawood proved that every planar graph with no 1-cycles is vertex 5-colorable, which is equivalent to the statement that every planar graph with no 1-bonds has a nowhere-zero 5-flow. Tutte has conjectured that every graph with no 1-bonds has a nowhere-zero 5-flow. We show that Tutte's 5-Flow Conjecture is true for all graphs embeddable in the real projective plane. 相似文献
13.
14.
D. W. Barnette 《Graphs and Combinatorics》1997,13(4):315-323
A graph with n vertices is said to have a small cycle cover provided its edges can be covered with at most (2n ? 1)/3 cycles. Bondy [2] has conjectured that every 2-connected graph has a small cycle cover. In [3] Lai and Lai prove Bondy’s conjecture for plane triangulations. In [1] the author extends this result to all planar 3-connected graphs, by proving that they can be covered by at most (n + 1)/2 cycles. In this paper we show that Bondy’s conjecture holds for all planar 2-connected graphs. We also show that all planar 2-edge-connected graphs can be covered by at most (3n ? 3)/4 cycles and we show an infinite family of graphs for which this bound is attained. 相似文献
15.
Cun-Quan Zhang 《Journal of Graph Theory》1990,14(5):537-546
It was conjectured by Fan that if a graph G = (V,E) has a nowhere-zero 3-flow, then G can be covered by two even subgraphs of total size at most |V| + |E| - 3. This conjecture is proved in this paper. It is also proved in this paper that the optimum solution of the Chinese postman problem and the solution of minimum cycle covering problem are equivalent for any graph admitting a nowhere-zero 4-flow. 相似文献
16.
It is known that the edge set of a 2-edge-connected 3-regular graph can be decomposed into paths of length 3. W. Li asked
whether the edge set of every 2-edge-connected graph can be decomposed into paths of length at least 3. The graphs C
3, C
4, C
5, and K
4−e have no such decompositions. We construct an infinite sequence {F
i
}
i=0
∞
of nondecomposable graphs. On the other hand, we prove that every other 2-edge-connected graph has a desired decomposition.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
17.
It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2t edges that shares an edge with each triangle of G. In this paper, we prove this conjecture for odd-wheel-free graphs and for ‘triangle-3-colorable’ graphs, where the latter
property means that the edges of the graph can be colored with three colors in such a way that each triangle receives three
distinct colors on its edges. Among the consequences we obtain that the conjecture holds for every graph with chromatic number
at most four. Also, two subclasses of K
4-free graphs are identified, in which the maximum number of pairwise edge-disjoint triangles is equal to the minimum number
of edges covering all triangles. In addition, we prove that the recognition problem of triangle-3-colorable graphs is intractable. 相似文献
18.
The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning
eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete.
Jaeger and Catlin independently showed that every 4-edge-connected graph has a spanning eulerian subgraph. In 1992, Zhan showed
that every 3-edge-connected, essentially 7-edge-connected graph has a spanning eulerian subgraph. It was conjectured in 1995
that every 3-edge-connected, essentially 5-edge-connected graph has a spanning eulerian subgraph. In this paper, we show that
if G is a 3-edge-connected, essentially 4-edge-connected graph and if for every pair of adjacent vertices u and v, d
G
(u) + d
G
(v) ≥ 9, then G has a spanning eulerian subgraph. 相似文献
19.
充分利用图的字典积的结构证明了以下结论:如果图G_1的每连通分支都非平凡,图G_2的阶数大于3,那么它们的字典积G_1[G_2]具有非零3-流. 相似文献
20.
Eckhard Steffen 《Discrete Mathematics》2010,310(3):385-389
In 1954, Tutte conjectured that every bridgeless graph has a nowhere-zero 5-flow. Let ω(G) be the minimum number of odd cycles in a 2-factor of a bridgeless cubic graph G. Tutte’s conjecture is equivalent to its restriction to cubic graphs with ω≥2. We show that if a cubic graph G has no edge cut with fewer than edges that separates two odd cycles of a minimum 2-factor of G, then G has a nowhere-zero 5-flow. This implies that if a cubic graph G is cyclically n-edge connected and , then G has a nowhere-zero 5-flow. 相似文献