共查询到20条相似文献，搜索用时 0 毫秒
1.
We show that for each rational number r such that 4<r?5 there exist infinitely many cyclically 4‐edge‐connected cubic graphs of chromatic index 4 and girth at least 5—that is, snarks—whose flow number equals r. This answers a question posed by Pan and Zhu [Construction of graphs with given circular flow numbers, J Graph Theory 43 [2003], 304–318]. © 2011 Wiley Periodicals, Inc. J Graph Theory 68: 189‐201, 2011 相似文献
2.
This article determines the set of the circular flow numbers of regular graphs. Let be the set of the circular flow numbers of graphs, and be the set of the circular flow numbers of d‐regular graphs. If d is even, then . For it is known 6 that . We show that . Hence, the interval is the only gap for circular flow numbers of ‐regular graphs between and 5. Furthermore, if Tutte's 5‐flow conjecture is false, then it follows, that gaps for circular flow numbers of graphs in the interval [5, 6] are due for all graphs not just for regular graphs. 相似文献
3.
In this paper, we characterize graphs whose tensor product admit nowhere‐zero 3‐flow. The main result is: For two graphs G1 and G2 with δ ≥ 2 and G2 not belonging to a well‐characterized class of graphs, the tensor product of G1 and G2 admits a nowhere‐zero 3‐flow. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 284–292, 2007 相似文献
4.
Bouchet's conjecture asserts that each signed graph which admits a nowhere‐zero flow has a nowhere‐zero 6‐flow. We verify this conjecture for two basic classes of signed graphs—signed complete and signed complete bipartite graphs by proving that each such flow‐admissible graph admits a nowhere‐zero 4‐flow and we characterise those which have a nowhere‐zero 2‐flow and a nowhere‐zero 3‐flow. 相似文献
5.
Let D be a t ‐ ( v, k , λ) design and let N i (D) , for 1 ≤ i ≤ t , be the higher incidence matrix of D , a ( 0 , 1 )‐matrix of size , where b is the number of blocks of D . A zero‐sum flow of D is a nowhere‐zero real vector in the null space of N 1 ( D ). A zero‐sum k‐flow of D is a zero‐sum flow with values in { 1 , …, ±( k ? 1 )}. In this article, we show that every non‐symmetric design admits an integral zero‐sum flow, and consequently we conjecture that every non‐symmetric design admits a zero‐sum 5‐flow. Similarly, the definition of zero‐sum flow can be extended to N i ( D ), 1 ≤ i ≤ t . Let be the complete design. We conjecture that N t ( D ) admits a zero‐sum 3‐flow and prove this conjecture for t = 2 . © 2011 Wiley Periodicals, Inc. J Combin Designs 19:355‐364, 2011 相似文献
6.
Hong‐Jian Lai 《Journal of Graph Theory》1999,30(4):277-288
7.
8.
Tutte's 3‐Flow Conjecture states that every 2‐edge‐connected graph with no 3‐cuts admits a 3‐flow. The 3‐Flow Conjecture is equivalent to the following: let G be a 2‐edge‐connected graph, let S be a set of at most three vertices of G; if every 3‐cut of G separates S then G has a 3‐flow. We show that minimum counterexamples to the latter statement are 3‐connected, cyclically 4‐connected, and cyclically 7‐edge‐connected. 相似文献
9.
A k‐weak bisection of a cubic graph G is a partition of the vertex‐set of G into two parts V1 and V2 of equal size, such that each connected component of the subgraph of G induced by () is a tree of at most vertices. This notion can be viewed as a relaxed version of nowhere‐zero flows, as it directly follows from old results of Jaeger that every cubic graph G with a circular nowhere‐zero r‐flow has a ‐weak bisection. In this article, we study problems related to the existence of k‐weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4‐weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5‐weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5‐flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges. 相似文献
10.
11.
Jensen and Toft 8 conjectured that every 2‐edge‐connected graph without a K5‐minor has a nowhere zero 4‐flow. Walton and Welsh 19 proved that if a coloopless regular matroid M does not have a minor in {M(K3,3), M*(K5)}, then M admits a nowhere zero 4‐flow. In this note, we prove that if a coloopless regular matroid M does not have a minor in {M(K5), M*(K5)}, then M admits a nowhere zero 4‐flow. Our result implies the Jensen and Toft conjecture. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
12.
Robert Šámal 《Journal of Graph Theory》2017,85(1):56-73
Given two graphs, a mapping between their edge‐sets is cycle‐continuous , if the preimage of every cycle is a cycle. The motivation for this definition is Jaeger's conjecture that for every bridgeless graph there is a cycle‐continuous mapping to the Petersen graph, which, if solved positively, would imply several other important conjectures (e.g., the Cycle double cover conjecture). Answering a question of DeVos, Ne?et?il, and Raspaud, we prove that there exists an infinite set of graphs with no cycle‐continuous mapping between them. Further extending this result, we show that every countable poset can be represented by graphs and the existence of cycle‐continuous mappings between them. 相似文献
13.
Tutte's 5‐flow conjecture from 1954 states that every bridgeless graph has a nowhere‐zero 5‐flow. It suffices to prove the conjecture for cyclically 6‐edge‐connected cubic graphs. We prove that every cyclically 6‐edge‐connected cubic graph with oddness at most 4 has a nowhere‐zero 5‐flow. This implies that every minimum counterexample to the 5‐flow conjecture has oddness at least 6. 相似文献
14.
Hong‐Jian Lai 《Journal of Graph Theory》2003,42(3):211-219
Let G be a graph. For each vertex v ∈V(G), Nv denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), Nv is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003 相似文献
15.
Martin Kochol 《Journal of Graph Theory》2002,40(3):137-146
The tension polynomial FG(k) of a graph G, evaluating the number of nowhere‐zero ?k‐tensions in G, is the nontrivial divisor of the chromatic polynomial χG(k) of G, in that χG(k) = kc(G)FG(k), where c(G) denotes the number of components of G. We introduce the integral tension polynomial IG(k), which evaluates the number of nowhere‐zero integral tensions in G with absolute values smaller than k. We show that 2r(G)FG(k)≥IG(k)≥ (r(G)+1)FG(k), where r(G)=|V(G)|?c(G), and, for every k>1, FG(k+1)≥ FG(k)˙k / (k?1) and IG(k+1)≥IG(k)˙k/(k?1). © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 137–146, 2002 相似文献
16.
Richard C. Bradley 《Journal of Graph Theory》2006,51(3):251-259
For a given snark G and a given edge e of G, let ψ(G, e) denote the nonnegative integer such that for a cubic graph conformal to G – {e}, the number of Tait colorings with three given colors is 18 · ψ(G, e). If two snarks G1 and G2 are combined in certain well‐known simple ways to form a snark G, there are some connections between ψ (G1, e1), ψ (G2, e2), and ψ(G, e) for appropriate edges e1, e2, and e of G1, G2, and G. As a consequence, if j and k are each a nonnegative integer, then there exists a snark G with an edge e such that ψ(G, e) = 2j · 3k. © 2005 Wiley Periodicals, Inc. 相似文献
17.
A snark is a cubic cyclically 4–edge connected graph with edge chromatic number four and girth at least five. We say that a graph G is odd 2–factored if for each 2–factor F of G each cycle of F is odd. In this extended abstract, we present a method for constructing odd 2–factored snarks. In particular, we construct two families of odd 2–factored snarks of order 26 and 34 that disprove a previous conjecture by some of the authors. 相似文献
18.
We study a new cardinal-valued invariant ndw(X) (calling it the nd-weight of X) of a topological space which is defined as the least upper bound of the weights of nowhere dense subsets of X. The main result is the proof of the inequality hl(X)ndw(X) for compact sets without isolated points ((hl is the hereditary Lindelof number). This inequality implies that a compact space without isolated points of countable nd-weight is completely normal. Assuming the continuum hypothesis, we construct an example of a nonmetrizable compact space of countable nd-weight without isolated points. 相似文献
19.
For a stationary Gaussian process either almost all sample paths are almost everywhere differentiable or almost all sample paths are almost nowhere differentiable. In this paper it is shown by means of an example involving a random lacunary trigonometric series that “almost everywhere differentiable” and “almost nowhere differentiable” cannot in general be replaced by “everywhere differentiable” and “nowhere differentiable”, respectively. 相似文献
20.
Y. A. Fiagbedzi 《International Journal of Mathematical Education in Science & Technology》2013,44(4):617-629
The coordinates of an n-dimensional regular simplex are found. These coordinates are used to derive properties of the regular simplex that generalize their two- and three-dimensional counterparts. 相似文献