首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 188 毫秒
1.
This paper considers a degree sum condition sufficient to imply the existence of k vertex-disjoint cycles in a graph G. For an integer t1, let σt(G) be the smallest sum of degrees of t independent vertices of G. We prove that if G has order at least 7k+1 and σ4(G)8k?3, with k2, then G contains k vertex-disjoint cycles. We also show that the degree sum condition on σ4(G) is sharp and conjecture a degree sum condition on σt(G) sufficient to imply G contains k vertex-disjoint cycles for k2.  相似文献   

2.
Let G be a balanced bipartite graph of order 2n4, and let σ1,1(G) be the minimum degree sum of two non-adjacent vertices in different partite sets of G. In 1963, Moon and Moser proved that if σ1,1(G)n+1, then G is hamiltonian. In this note, we show that if k is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly k cycles for sufficiently large graphs. In order to prove this, we also give a σ1,1 condition for the existence of k vertex-disjoint alternating cycles with respect to a chosen perfect matching in G.  相似文献   

3.
An edge-coloured graph G is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph G, denoted by pc(G), is the smallest number of colours that are needed in order to make G properly connected. Our main result is the following: Let G be a connected graph of order n and k2. If |E(G)|n?k?12+k+2, then pc(G)k except when k=2 and G{G1,G2}, where G1=K1(2K1+K2) and G2=K1(K1+2K2).  相似文献   

4.
5.
Let S be a set of at least two vertices in a graph G. A subtree T of G is a S-Steiner tree if S?V(T). Two S-Steiner trees T1 and T2 are edge-disjoint (resp. internally vertex-disjoint) if E(T1)E(T2)=? (resp. E(T1)E(T2)=? and V(T1)V(T2)=S). Let λG(S) (resp. κG(S)) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) S-Steiner trees in G, and let λk(G) (resp. κk(G)) be the minimum λG(S) (resp. κG(S)) for S ranges over all k-subset of V(G). Kriesell conjectured that if λG({x,y})2k for any x,yS, then λG(S)k. He proved that the conjecture holds for |S|=3,4. In this paper, we give a short proof of Kriesell’s Conjecture for |S|=3,4, and also show that λk(G)1k?1k?2 (resp. κk(G)1k?1k?2 ) if λ(G)? (resp. κ(G)?) in G, where k=3,4. Moreover, we also study the relation between κk(L(G)) and λk(G), where L(G) is the line graph of G.  相似文献   

6.
7.
8.
9.
10.
A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define Vi?{vV(G):c(v)=i} for i=1 and 2. We say that G is (d1,d2)-colorable if G has a 2-coloring such that Vi is an empty set or the induced subgraph G[Vi] has the maximum degree at most di for i=1 and 2. Let G be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether G is (0,k)-colorable is NP-complete for every positive integer k. Moreover, we construct non-(1,k)-colorable planar graphs without 4-cycles and 5-cycles for every positive integer k. In contrast, we prove that G is (d1,d2)-colorable where (d1,d2)=(4,4),(3,5), and (2,9).  相似文献   

11.
The generalized Ramsey number R(G1,G2) is the smallest positive integer N such that any red–blue coloring of the edges of the complete graph KN either contains a red copy of G1 or a blue copy of G2. Let Cm denote a cycle of length m and Wn denote a wheel with n+1 vertices. In 2014, Zhang, Zhang and Chen determined many of the Ramsey numbers R(C2k+1,Wn) of odd cycles versus larger wheels, leaving open the particular case where n=2j is even and k<j<3k2. They conjectured that for these values of j and k, R(C2k+1,W2j)=4j+1. In 2015, Sanhueza-Matamala confirmed this conjecture asymptotically, showing that R(C2k+1,W2j)4j+334. In this paper, we prove the conjecture of Zhang, Zhang and Chen for almost all of the remaining cases. In particular, we prove that R(C2k+1,W2j)=4j+1 if j?k251, k<j<3k2, and j212299.  相似文献   

12.
13.
Let G=(VE) be a simple graph and for every vertex vV let L(v) be a set (list) of available colors. G is called L-colorable if there is a proper coloring φ of the vertices with φ(v)L(v) for all vV. A function f:VN is called a choice function of G and G is said to be f-list colorable if G is L-colorable for every list assignment L choice function is defined by size(f)=vVf(v) and the sum choice number χsc(G) denotes the minimum size of a choice function of G.Sum list colorings were introduced by Isaak in 2002 and got a lot of attention since then.For r3 a generalized θk1k2kr-graph is a simple graph consisting of two vertices v1 and v2 connected by r internally vertex disjoint paths of lengths k1,k2,,kr (k1k2?kr).In 2014, Carraher et al. determined the sum-paintability of all generalized θ-graphs which is an online-version of the sum choice number and consequently an upper bound for it.In this paper we obtain sharp upper bounds for the sum choice number of all generalized θ-graphs with k12 and characterize all generalized θ-graphs G which attain the trivial upper bound |V(G)|+|E(G)|.  相似文献   

14.
Fuhong Ma  Jin Yan 《Discrete Mathematics》2018,341(10):2903-2911
Let t and k be two integers with t5 and k2. For a graph G and a vertex x of G, we use dG(x) to denote the degree of x in G. Define σt(G) to be the minimum value of xXdG(x), where X is an independent set of G with |X|=t. This paper proves the following conjecture proposed by Gould et al. (2018). If G is a graph of sufficiently large order with σt(G)2kt?t+1, then G contains k vertex-disjoint cycles.  相似文献   

15.
16.
For i=2,3 and a cubic graph G let νi(G) denote the maximum number of edges that can be covered by i matchings. We show that ν2(G)45|V(G)| and ν3(G)76|V(G)|. Moreover, it turns out that ν2(G)|V(G)|+2ν3(G)4.  相似文献   

17.
18.
For bipartite graphs G1,G2,,Gk, the bipartite Ramsey number b(G1,G2,,Gk) is the least positive integer b so that any coloring of the edges of Kb,b with k colors will result in a copy of Gi in the ith color for some i. In this paper, our main focus will be to bound the following numbers: b(C2t1,C2t2) and b(C2t1,C2t2,C2t3) for all ti3,b(C2t1,C2t2,C2t3,C2t4) for 3ti9, and b(C2t1,C2t2,C2t3,C2t4,C2t5) for 3ti5. Furthermore, we will also show that these mentioned bounds are generally better than the bounds obtained by using the best known Zarankiewicz-type result.  相似文献   

19.
20.
TextFor any given two positive integers k1 and k2, and any set A of nonnegative integers, let rk1,k2(A,n) denote the number of solutions of the equation n=k1a1+k2a2 with a1,a2A. In this paper, we determine all pairs k1,k2 of positive integers for which there exists a set A?N such that rk1,k2(A,n)=rk1,k2(N?A,n) for all n?n0. We also pose several problems for further research.VideoFor a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=EnezEsJl0OY.  相似文献   

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

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