共查询到20条相似文献,搜索用时 188 毫秒
1.
This paper considers a degree sum condition sufficient to imply the existence of vertex-disjoint cycles in a graph . For an integer , let be the smallest sum of degrees of independent vertices of . We prove that if has order at least and , with , then contains vertex-disjoint cycles. We also show that the degree sum condition on is sharp and conjecture a degree sum condition on sufficient to imply contains vertex-disjoint cycles for . 相似文献
2.
A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs
Let be a balanced bipartite graph of order , and let be the minimum degree sum of two non-adjacent vertices in different partite sets of . In 1963, Moon and Moser proved that if , then is hamiltonian. In this note, we show that if is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly cycles for sufficiently large graphs. In order to prove this, we also give a condition for the existence of vertex-disjoint alternating cycles with respect to a chosen perfect matching in . 相似文献
3.
Susan A. van Aardt Christoph Brause Alewyn P. Burger Marietjie Frick Arnfried Kemnitz Ingo Schiermeyer 《Discrete Mathematics》2017,340(11):2673-2677
An edge-coloured graph 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 denoted by , is the smallest number of colours that are needed in order to make properly connected. Our main result is the following: Let be a connected graph of order and . If , then except when and where and 相似文献
4.
5.
Let be a set of at least two vertices in a graph . A subtree of is a -Steiner tree if . Two -Steiner trees and are edge-disjoint (resp. internally vertex-disjoint) if (resp. and ). Let (resp. ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) -Steiner trees in , and let (resp. ) be the minimum (resp. ) for ranges over all -subset of . Kriesell conjectured that if for any , then . He proved that the conjecture holds for . In this paper, we give a short proof of Kriesell’s Conjecture for , and also show that (resp. ) if (resp. ) in , where . Moreover, we also study the relation between and , where is the line graph of . 相似文献
6.
7.
8.
9.
10.
A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define for and We say that is -colorable if has a 2-coloring such that is an empty set or the induced subgraph has the maximum degree at most for and Let be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether is -colorable is NP-complete for every positive integer Moreover, we construct non--colorable planar graphs without 4-cycles and 5-cycles for every positive integer In contrast, we prove that is -colorable where and 相似文献
11.
Ryan Alweiss 《Discrete Mathematics》2018,341(4):981-989
The generalized Ramsey number is the smallest positive integer such that any red–blue coloring of the edges of the complete graph either contains a red copy of or a blue copy of . Let denote a cycle of length and denote a wheel with vertices. In 2014, Zhang, Zhang and Chen determined many of the Ramsey numbers of odd cycles versus larger wheels, leaving open the particular case where is even and . They conjectured that for these values of and , . In 2015, Sanhueza-Matamala confirmed this conjecture asymptotically, showing that . In this paper, we prove the conjecture of Zhang, Zhang and Chen for almost all of the remaining cases. In particular, we prove that if , , and . 相似文献
12.
13.
Christoph Brause Arnfried Kemnitz Massimiliano Marangio Anja Pruchnewski Margit Voigt 《Discrete Mathematics》2017,340(11):2633-2640
Let be a simple graph and for every vertex let be a set (list) of available colors. is called -colorable if there is a proper coloring of the vertices with for all . A function is called a choice function of and is said to be -list colorable if is -colorable for every list assignment choice function is defined by and the sum choice number
denotes the minimum size of a choice function of .Sum list colorings were introduced by Isaak in 2002 and got a lot of attention since then.For a generalized
-graph is a simple graph consisting of two vertices and connected by internally vertex disjoint paths of lengths
.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 and characterize all generalized -graphs which attain the trivial upper bound . 相似文献
14.
Let and be two integers with and . For a graph and a vertex of , we use to denote the degree of in . Define to be the minimum value of , where is an independent set of with . This paper proves the following conjecture proposed by Gould et al. (2018). If is a graph of sufficiently large order with , then contains vertex-disjoint cycles. 相似文献
15.
16.
Vahan V. Mkrtchyan Samvel S. Petrosyan Gagik N. Vardanyan 《Discrete Mathematics》2010,310(10-11):1588-1613
For and a cubic graph let denote the maximum number of edges that can be covered by matchings. We show that and . Moreover, it turns out that . 相似文献
17.
18.
For bipartite graphs , the bipartite Ramsey number is the least positive integer so that any coloring of the edges of with colors will result in a copy of in the th color for some . In this paper, our main focus will be to bound the following numbers: and for all for and for 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.
《Discrete Mathematics》2007,307(17-18):2209-2216
20.
TextFor any given two positive integers and , and any set A of nonnegative integers, let denote the number of solutions of the equation with . In this paper, we determine all pairs of positive integers for which there exists a set such that for all . 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. 相似文献