共查询到20条相似文献,搜索用时 31 毫秒
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.
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.
6.
7.
8.
9.
Let be a finite group, written multiplicatively. The Davenport constant of is the smallest positive integer such that every sequence of with elements has a non-empty subsequence with product . Let be the Dihedral Group of order and be the Dicyclic Group of order . Zhuang and Gao (2005) showed that and Bass (2007) showed that . In this paper, we give explicit characterizations of all sequences of such that and is free of subsequences whose product is 1, where is equal to or for some . 相似文献
10.
Let G be a graph with n vertices and edges, and let be the Laplacian eigenvalues of G. Let , where . Brouwer conjectured that for . It has been shown in Haemers et al. [7] that the conjecture is true for trees. We give upper bounds for , and in particular, we show that the conjecture is true for unicyclic and bicyclic graphs. 相似文献
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.
Let be a -connected graph of order . In [1], Bondy (1980) considered a degree sum condition for a graph to have a Hamiltonian cycle, say, to be covered by one cycle. He proved that if , then has a Hamiltonian cycle. On the other hand, concerning a degree sum condition for a graph to be covered by two cycles, Enomoto et al. (1995) [4] proved that if and , then can be covered by two cycles. By these results, we conjecture that if , then can be covered by two cycles. In this paper, we prove the case of this conjecture. In fact, we prove a stronger result; if is 2-connected with , then can be covered by two cycles, or belongs to an exceptional class. 相似文献
13.
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 相似文献
14.
《Discrete Mathematics》2007,307(17-18):2209-2216
15.
16.
Bart Litjens 《Discrete Mathematics》2018,341(6):1740-1748
17.
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 . 相似文献
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.
20.