首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Chvátal established that r(Tm, Kn) = (m – 1)(n – 1) + 1, where Tm is an arbitrary tree of order m and Kn is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed Kn could be replaced by a graph with clique number n and order n + 1 provided n ≧ 3 and m ≧ 3. We further extend these results to show that Kn can be replaced by any graph on n + 2 vertices with clique number n, provided n ≧ 5 and m ≧ 4. We then show that further extensions, in particular to graphs on n + 3 vertices with clique number n are impossible. We also investigate the Ramsey number of trees versus complete graphs minus sets of independent edges. We show that r(Tm, Kn –tK2) = (m – 1)(n – t – 1) + 1 for m ≧ 3, n ≧ 6, where Tm is any tree of order m except the star, and for each t, O ≦ t ≦ [(n – 2)/2].  相似文献   

2.
For an arbitrary tree T of order m and an arbitrary positive integer n, Chvátal proved that the Ramsey number r(T, Kn) = 1 + (m ? 1) (n ? 1). for graphs G, G1, and G2, we say that G arrows G1 and G2, written G → (G1, G2), if for every factorization G = RB, either G1 is a subgraph of R or G2 is a subgraph of B. it is shown that (i) for each l ≥ 2, K1+ (m?1)(n?1) ?E(K1) → (T, Kn) for m ≥ 2/ ? 1 and n ≥ 2; (ii) K1 +,(m ?1)(n ?1) ? E(H) → (T, Kn), where H is any tree of order m ? 1, m ≥ 3 and n ≥ 2. It is further shown that result (i) is sharp with respect to the inequality m2/? 1; in particular, examples are given to show that K1 + (2l?3)(n?1) E(K1) ? (P21?2, Kn) for all n ≥ 2, where P21?2 denotes the path of order 21 ? 2. Also result (ii) is sharp with respect to the order of H; examples aregiven to show that K1 + (m?1)(n?1)? E(K(1, m ? 1)) ?(T, Kn)for any tree T of order m and any n ≥ 2.  相似文献   

3.
Zarankiewicz's conjecture, that the crossing number of the complete-bipartite graph Km, n is [1/2 m] [1/2 (m] ?1) [1/2 n] [1/2 (n ?1)], was proved by Kleitman when min(m, n) ≤ 6, but was unsettled in all other cases. The cyclic-order graph COn arises naturally in the study of this conjecture; it is a vertex-transitive harmonic diametrical (even) graph. In this paper the properties of cyclic-order graphs are investigated and used as the basis for computer programs that have verified Zarankiewicz's conjecture for K7,7 and K7,9; thus the smallest unsettled cases are now K7,11 and K9,9. © 1993 John Wiley & Sons, Inc.  相似文献   

4.
The cycle‐complete graph Ramsey number r(Cm, Kn) is the smallest integer N such that every graph G of order N contains a cycle Cm on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(Cm, Kn) = (m ? 1) (n ? 1) + 1 for all mn ≥ 3 (except r(C3, K3) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with mn2 ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003  相似文献   

5.
The spectrum of path factorization of bipartite multigraphs   总被引:1,自引:0,他引:1  
LetλK_(m,n)be a bipartite multigraph with two partite sets having m and n vertices, respectively.A P_v-factorization ofλK_(m,n)is a set of edge-disjoint P_v-factors ofλK_(m,n)which partition the set of edges ofλK_(m,n).When v is an even number,Ushio,Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P_v-factorization ofλK_(m,n).When v is an odd number,we have proposed a conjecture.Very recently,we have proved that the conjecture is true when v=4k-1.In this paper we shall show that the conjecture is true when v = 4k 1,and then the conjecture is true.That is,we will prove that the necessary and sufficient conditions for the existence of a P_(4k 1)-factorization ofλK_(m,n)are(1)2km≤(2k 1)n,(2)2kn≤(2k 1)m,(3)m n≡0(mod 4k 1),(4)λ(4k 1)mn/[4k(m n)]is an integer.  相似文献   

6.
 We establish necessary and sufficient conditions for the existence of a spanning tree factorization of the complete bipartite graph K m,n. Received: September 1, 1997 Revised: June 29, 1998  相似文献   

7.
In this article, we study the existence of a 2‐factor in a K1, n‐free graph. Sumner [J London Math Soc 13 (1976), 351–359] proved that for n?4, an (n?1)‐connected K1, n‐free graph of even order has a 1‐factor. On the other hand, for every pair of integers m and n with m?n?4, there exist infinitely many (n?2)‐connected K1, n‐free graphs of even order and minimum degree at least m which have no 1‐factor. This implies that the connectivity condition of Sumner's result is sharp, and we cannot guarantee the existence of a 1‐factor by imposing a large minimum degree. On the other hand, Ota and Tokuda [J Graph Theory 22 (1996), 59–64] proved that for n?3, every K1, n‐free graph of minimum degree at least 2n?2 has a 2‐factor, regardless of its connectivity. They also gave examples showing that their minimum degree condition is sharp. But all of them have bridges. These suggest that the effects of connectivity, edge‐connectivity and minimum degree to the existence of a 2‐factor in a K1, n‐free graph are more complicated than those to the existence of a 1‐factor. In this article, we clarify these effects by giving sharp minimum degree conditions for a K1, n‐free graph with a given connectivity or edge‐connectivity to have a 2‐factor. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 68:77‐89, 2011  相似文献   

8.
A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that (1) m ≤ kn, (2) n ≤ km, (3) km-n = kn-m ≡ 0 (mod (k^2- 1)) and (4) λ(km-n)(kn-m) ≡ 0 (mod k(k- 1)(k^2 - 1)(m + n)).  相似文献   

9.
Graham and Pollak [3] proved that n ?1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of Kn can be decomposed. Using a linear algebraic technique, Tverberg [2] gives a different proof of that result. We apply his technique to show that for “almost all n,” ? (n + m ?3)/(m ?1) ? is the minimum number of edge-disjoint complete m-partite subgraphs in a decomposition of Kn.  相似文献   

10.
Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing number of the Cartesian products of paths, cycles or stars with small graphs. In this paper we study cr(KmPn), the crossing number of the Cartesian product KmPn. We prove that for m ≥ 3,n ≥ 1 and cr(KmPn)≥ (n − 1)cr(Km+2e) + 2cr(Km+1). For m≤ 5, according to Klešč, Jendrol and Ščerbová, the equality holds. In this paper, we also prove that the equality holds for m = 6, i.e., cr(K6Pn) = 15n + 3. Research supported by NFSC (60373096, 60573022).  相似文献   

11.
Ervin Győri 《Combinatorica》1991,11(3):231-243
In this paper, we prove that any graph ofn vertices andt r–1(n)+m edges, wheret r–1(n) is the Turán number, contains (1–o(1)m edge disjointK r'sifm=o(n 2). Furthermore, we determine the maximumm such that every graph ofn vertices andt r–1(n)+m edges containsm edge disjointK r's ifn is sufficiently large.Research partially supported by Hungarian National Foundation for Scientific Research Grant no. 1812.  相似文献   

12.
For integers m, n ≥ 2, let g(m, n) be the minimum order of a graph, where every vertex belongs to both a clique Km of order m and a biclique K(n, n). We show that g(m, n) = 2(m + n − 2) if mn − 2. Furthermore, for mn − 1, we establish that ≡ 0 mod(n − 1) or, if m is sufficiently large and is not an integer. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 60–66, 2000  相似文献   

13.
It has been conjectured that r(Cm, Kn) = (m − 1)(n − 1) + 1 for all mn ≥ 4. This has been proved recently for n = 4 and n = 5. In this paper, we prove that r(C5, K6) = 21. This raises the possibility that r(Cm, K6) = 5m − 4 for all m ≥ 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 99–108, 2000  相似文献   

14.
An upper bound on the Ramsey number r(K2,n‐s,K2,n) where s ≥ 2 is presented. Considering certain r(K2,n‐s,K2,n)‐colorings obtained from strongly regular graphs, we additionally prove that this bound matches the exact value of r(K2,n‐s,K2,n) in infinitely many cases if holds. Moreover, the asymptotic behavior of r(K2,m,K2,n) is studied for n being sufficiently large depending on m. We conclude with a table of all known Ramsey numbers r(K2,m,K2,n) where m,n ≤ 10. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 252–268, 2003  相似文献   

15.
Let αm(n) denote the minimum number of edge-disjoint complete m-partite subgraphs into which Kn can be decomposed. In [2] the author proved that when m ≥ 3, if (i) nm and nm (mod m ?1), or (ii) b ∈ [2, m ?1], nb(m ?1) + m ? (b ?1), and nb(m ?1) + m ? (b ?1) (mod m? 1), then αm(n) = ?(n + m ?3)/(m ?1)? (= ?(n ?1)/(m ?1)?), and that for every integer n, if Kn has an edge-disjoint complete m-partite subgraph decomposition, then αm(n) ≥ ?(n? 1)/(m? 1)?. In this paper we generally discuss the question as to which integers n's satisfy (or do not) αm(n) = ?(n ?1)/(m ?1)?. Here we also study the methods to find these integers; the methods are themselves interesting. Our main results are Theorem 2.11, 2.12, and 2.16. Besides, Theorem 2.4 and 2.6 are interesting results too. © 1993 John Wiley & Sons, Inc.  相似文献   

16.
With the proof of the Evans conjecture, it was established that any partial latin square of side n with a most n ? 1 nonempty cells can be completed to a latin square of side n. In this article we prove an analogous result for symmetric latin squares: a partial symmetric latin square of side n with an admissible diagonal and at most n ? 1 nonempty cells can be completed to a symmetric latin square of side n. We also characterize those partial symmetric latin squares of side n with exactly n or n + 1 nonempty cells which cannot be completed. From these results we deduce theorems about completing edge-colorings of complete graphs K2m and K2m ? 1 with 2m ? 1 colors, with m + 1 or fewer edges getting prescribed colors. © 1994 John Wiley & Sons, Inc.  相似文献   

17.
Let λK m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P v-factorization of λK m,n is a set of edge-disjoint P v -factors of λK m,n which partition the set of edges of λK m,n. When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P v -factorization of λK m,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for v = 3. In this paper we will show that the conjecture is true when v = 4k − 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P 4k−1-factorization of λK m,n is (1) (2k − 1)m ⩽ 2kn, (2) (2k − 1)n ⩽ 2km, (3) m + n ≡ 0 (mod 4k − 1), (4) λ(4k − 1)mn/[2(2k − 1)(m + n)] is an integer.  相似文献   

18.
 In this paper we study three-color Ramsey numbers. Let K i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G 1, G 2 and G 3, if r(G 1, G 2)≥s(G 3), then r(G 1, G 2, G 3)≥(r(G 1, G 2)−1)(χ(G 3)−1)+s(G 3), where s(G 3) is the chromatic surplus of G 3; (ii) (k+m−2)(n−1)+1≤r(K 1,k , K 1,m , K n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed mk≥2, there is a constant c such that r(K k,m , K k,m , K n )≤c(n/logn), and r(C 2m , C 2m , K n )≤c(n/logn) m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55  相似文献   

19.
In this article, it is proved that for each even integer m?4 and each admissible value n with n>2m, there exists a cyclic m‐cycle system of Kn, which almost resolves the existence problem for cyclic m‐cycle systems of Kn with m even. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:23–39, 2012  相似文献   

20.
For fixed integers m,k2, it is shown that the k-color Ramsey number rk(Km,n) and the bipartite Ramsey number bk(m,n) are both asymptotically equal to kmn as n→∞, and that for any graph H on m vertices, the two-color Ramsey number is at most (1+o(1))nm+1/(logn)m-1. Moreover, the order of magnitude of is proved to be nm+1/(logn)m if HKm as n→∞.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号