首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 125 毫秒
1.
 Let G=(V 1,V 2;E) be a bipartite graph with 2km=|V 1|≤|V 2|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs. Received: December 9, 1998 Final version received: June 2, 1999  相似文献   

2.
 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s 3(G) ≥ 2 k −3, where s r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s 3(G) < 2 k −2, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000  相似文献   

3.
(3,k)-Factor-Critical Graphs and Toughness   总被引:1,自引:0,他引:1  
 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and kn−7. Revised: September 21, 1998  相似文献   

4.
The multicolor Ramsey number Rr(H) is defined to be the smallest integer n=n(r) with the property that any r-coloring of the edges of the complete graph Kn must result in a monochromatic subgraph of Kn isomorphic to H. It is well known that 2rm<Rr(C2m+1)<2(r+2)!m and Rr(C2m)≥(r−1)(m−1)+1. In this paper, we prove that Rr(C2m)≥2(r−1)(m−1)+2. This research is supported by NSFC(60373096, 60573022) and SRFDP(20030141003)  相似文献   

5.
 For an ordered k-decomposition ? = {G 1, G 2,…,G k } of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G 1), d(e, G 2),…,d(e, G k )), where d(e, G i ) is the distance from e to G i . A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K n ) ≤⌊(2n + 5)/3⌋ for n≥ 3. Received: June 17, 1998 Final version received: August 10, 1999  相似文献   

6.
Asymptotic Upper Bounds for Ramsey Functions   总被引:5,自引:0,他引:5  
 We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf a +1(d), where f a +1(d)=∫0 1(((1−t)1/( a +1))/(a+1+(da−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K k + l ,K n )≤ (l+o(1))n k /(logn) k −1. In particular, r(K k , K n )≤(1+o(1))n k −1/(log n) k −2. Received: May 11, 1998 Final version received: March 24, 1999  相似文献   

7.
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)).  相似文献   

8.
For a graph G, we define σ2(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v 1,...,v k , G has k vertex-disjoint cycles C 1,..., C k of length at most four such that v i V(C i ) for all 1 ≤ ik. And show if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v 1,...,v k , G has k vertex-disjoint cycles C 1,..., C k such that v i V(C i ) for all 1 ≤ i ≤ k, V(C 1) ∪...∪ V(C k ) = V(G), and |C i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ2(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.  相似文献   

9.
Hom(G, H) is a polyhedral complex defined for any two undirected graphsG andH. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes. We prove that Hom(K m, Kn) is homotopy equivalent to a wedge of (nm)-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graphG, and integersm≥2 andk≥−1, we have ϖ 1 k (Hom(K m, G))≠0, thenχ(G)≥k+m; here ℤ2-action is induced by the swapping of two vertices inK m, and ϖ1 is the first Stiefel-Whitney class corresponding to this action. Furthermore, we prove that a fold in the first argument of Hom(G, H) induces a homotopy equivalence. It then follows that Hom(F, K n) is homotopy equivalent to a direct product of (n−2)-dimensional spheres, while Hom(F, K n) is homotopy equivalent to a wedge of spheres, whereF is an arbitrary forest andF is its complement. The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation Grant PP002-102738/1, the University of Bern, and the Royal Institute of Technology, Stockholm.  相似文献   

10.
A non-complete graph G is called an (n,k)-graph if it is n-connected but GX is not (n−|X|+1)-connected for any X V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism). Here we prove this conjecture.  相似文献   

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

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