共查询到20条相似文献,搜索用时 31 毫秒
1.
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 相似文献
2.
In this paper we investigate to what extent the results of Z. Wang and D. Daigle on “nice derivations” of the polynomial ring over a field k of characteristic zero extend to the polynomial ring over a PID R, containing the field of rational numbers. One of our results shows that the kernel of a nice derivation on of rank at most three is a polynomial ring over k. 相似文献
3.
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 . 相似文献
4.
5.
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 . 相似文献
6.
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. 相似文献
7.
8.
9.
10.
Jessica De Silva Kristin Heysse Adam Kapilow Anna Schenfisch Michael Young 《Discrete Mathematics》2018,341(2):492-496
For two graphs and , the Turán number is the maximum number of edges in a subgraph of that contains no copy of . Chen, Li, and Tu determined the Turán numbers for all Chen et al. (2009). In this paper we will determine the Turán numbers for all and . 相似文献
11.
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. 相似文献
12.
13.
Let e be a positive integer, p be an odd prime, , and be the finite field of q elements. Let . The graph is a bipartite graph with vertex partitions and , and edges defined as follows: a vertex is adjacent to a vertex if and only if and . If and , the graph contains no cycles of length less than eight and is edge-transitive. Motivated by certain questions in extremal graph theory and finite geometry, people search for examples of graphs containing no cycles of length less than eight and not isomorphic to the graph , even without requiring them to be edge-transitive. So far, no such graphs have been found. It was conjectured that if both f and g are monomials, then no such graphs exist. In this paper we prove the conjecture. 相似文献
14.
Shuya Chiba 《Discrete Mathematics》2018,341(10):2912-2918
For a vertex subset of a graph , let be the maximum value of the degree sums of the subsets of of size . In this paper, we prove the following result: Let be positive integers, and let be an -connected graph of order . If for every independent set of size in , then has a 2-factor with exactly cycles. This is a common extension of the results obtained by Brandt et al. (1997) and Yamashita (2008), respectively. 相似文献
15.
16.
17.
Let be a graph of order . An even squared Hamiltonian cycle (ESHC) of is a Hamiltonian cycle of with chords for all (where for ). When is even, an ESHC contains all bipartite -regular graphs of order . We prove that there is a positive integer such that for every graph of even order , if the minimum degree is , then contains an ESHC. We show that the condition of being even cannot be dropped and the constant cannot be replaced by . Our results can be easily extended to even th powered Hamiltonian cycles for all . 相似文献
18.
A packing-coloring of a graph is a partition of into sets such that for each the distance between any two distinct is at least . The packing chromatic number, , of a graph is the minimum such that has a packing -coloring. Sloper showed that there are -regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed and , almost every -vertex cubic graph of girth at least has the packing chromatic number greater than . 相似文献
19.
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. 相似文献
20.
S. Akbari D. Cariolaro M. Chavooshi M. Ghanbari S. Zare 《Discrete Mathematics》2012,312(17):2593-2598