共查询到20条相似文献,搜索用时 406 毫秒
1.
The Delannoy numbers count the number of lattice paths from to using steps and . We show that the zeros of all Delannoy polynomials are in the open interval and are dense in the corresponding closed interval. We also show that the Delannoy numbers are asymptotically normal (by central and local limit theorems). 相似文献
2.
3.
《Discrete Mathematics》2022,345(7):112886
In this article we investigate a problem in graph theory, which has an equivalent reformulation in extremal set theory similar to the problems researched in “A general 2-part Erd?s-Ko-Rado theorem” by Gyula O.H. Katona, who proposed our problem as well. In the graph theoretic form we examine the clique number of the Xor product of two isomorphic Kneser graphs. Denote this number with . We give lower and upper bounds on , and we solve the problem up to a constant deviation depending only on k, and find the exact value for if N is large enough. Also we compute that is asymptotically equivalent to . 相似文献
4.
5.
Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs and , the -colored Gallai–Ramsey number is defined to be the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete graph contains a monochromatic copy of . In this paper, we first provide some exact values and bounds of . Moreover, we define the -colored bipartite Gallai–Ramsey number as the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete bipartite graph contains a monochromatic copy of . Furthermore, we describe the structures of complete bipartite graph with no rainbow and , respectively. Finally, we find the exact values of (), (where is a subgraph of ), and by using the structural results. 相似文献
6.
7.
The tensor product of graphs , and is defined by and Let be the fractional chromatic number of a graph . In this paper, we prove that if one of the three graphs , and is a circular clique, 相似文献
8.
We consider the structure of -free subgraphs of graphs with high minimal degree. We prove that for every there exists an so that the following holds. For every graph with chromatic number from which one can delete an edge and reduce the chromatic number, and for every graph on vertices in which all degrees are at least , any subgraph of which is -free and contains the maximum number of copies of the complete graph is -colorable.We also consider several extensions for the case of a general forbidden graph of a given chromatic number, and for subgraphs maximizing the number of copies of balanced blowups of complete graphs. 相似文献
9.
《Discrete Mathematics》2022,345(5):112801
Let G and H be simple graphs. The Ramsey number is the minimum integer N such that any red-blue-coloring of edges of contains either a red copy of G or a blue copy of H. Let denote m vertex-disjoint copies of . A lower bound is that . Burr, Erd?s and Spencer proved that this bound is indeed the Ramsey number for , and . In this paper, we show that this bound is the Ramsey number for and . We also show that this bound is the Ramsey number for and . 相似文献
10.
11.
《Discrete Mathematics》2019,342(4):1028-1037
For a given pair of two graphs , let be the smallest positive integer such that for any graph of order , either contains as a subgraph or the complement of contains as a subgraph. Baskoro, Broersma and Surahmat (2005) conjectured that for , where is the join of and . In this paper, we prove that this conjecture is true for the case . 相似文献
12.
Let be the -color Ramsey number of an odd cycle of length . It is shown that for each fixed , for all sufficiently large , where is a constant. This improves an old result by Bondy and Erd?s (1973). 相似文献
13.
14.
15.
For given graphs , , the -color Ramsey number, denoted by , is the smallest integer such that if we arbitrarily color the edges of a complete graph of order with colors, then it always contains a monochromatic copy of colored with , for some . Let be a cycle of length and a star of order . In this paper, firstly we give a general upper bound of . In particular, for the 3-color case, we have and this bound is tight in some sense. Furthermore, we prove that for all and , and if is a prime power, then the equality holds. 相似文献
16.
17.
《Discrete Mathematics》2022,345(3):112731
Let be the matching number of a graph G. A characterization of the graphs with given maximum odd degree and smallest possible matching number is given by Henning and Shozi (2021) [13]. In this paper we complete our study by giving a characterization of the graphs with given maximum even degree and smallest possible matching number. In 2018 Henning and Yeo [10] proved that if G is a connected graph of order n, size m and maximum degree k where is even, then , unless G is k-regular and . In this paper, we give a complete characterization of the graphs that achieve equality in this bound when the maximum degree k is even, thereby completing our study of graphs with given maximum degree and smallest possible matching number. 相似文献
18.
Let be a simple connected graph with vertices and edges. The spectral radius of is the largest eigenvalue of its adjacency matrix. In this paper, we firstly consider the effect on the spectral radius of a graph by removing a vertex, and then as an application of the result, we obtain a new sharp upper bound of which improves some known bounds: If , where is an integer, then The equality holds if and only if is a complete graph or , where is the graph obtained from by deleting some edge . 相似文献
19.
20.
In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials and . Then, he defined and to be the polynomials satisfying and . In this paper, we give a combinatorial interpretation of the coefficients of and prove a symmetry of the coefficients, i.e., . We give a combinatorial interpretation of and prove that is a polynomial in with non-negative integer coefficients. We also prove that if then all coefficients of except the coefficient of are non-negative integers. For all , the coefficient of in is , and when some other coefficients of are also negative. 相似文献