共查询到20条相似文献,搜索用时 31 毫秒
1.
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). 相似文献
2.
《Discrete Mathematics》2019,342(2):344-351
Mader (2010) conjectured that for every positive integer and every finite tree with order , every -connected, finite graph with contains a subtree isomorphic to such that is -connected. The conjecture has been verified for paths, trees when , and stars or double-stars when . In this paper we verify the conjecture for two classes of trees when .For digraphs, Mader (2012) conjectured that every -connected digraph with minimum semi-degree for a positive integer has a dipath of order with . The conjecture has only been verified for the dipath with , and the dipath with and . In this paper, we prove that every strongly connected digraph with minimum semi-degree contains an oriented tree isomorphic to some given oriented stars or double-stars with order such that is still strongly connected. 相似文献
3.
4.
5.
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. 相似文献
6.
7.
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 . 相似文献
8.
We give methods for constructing many self-dual -codes and Type II -codes of length 2n starting from a given self-dual -code and Type II -code of length 2n, respectively. As an application, we construct extremal Type II -codes of length 24 for and extremal Type II -codes of length 32 for . We also construct new extremal Type II -codes of lengths 56 and 64. 相似文献
9.
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). 相似文献
10.
11.
For a connected amply regular graph with parameters satisfying , it is known that its diameter is bounded by . This was generalized by Terwilliger to -graphs satisfying . It follows from Terwilliger that a connected amply regular graph with parameters satisfying and has diameter at most 7.In this paper we will classify the 2-walk-regular graphs with valency and diameter at least 4 such that its intersection number satisfies . This result generalizes a result of Koolen and Park for distance-regular graphs. And we show that if such a 2-walk-regular graph is not distance-regular, then it is the incidence graph of a group divisible design with the dual property with parameters . 相似文献
12.
13.
14.
We construct orthogonal arrays (of strength two) having a row that is repeated times, where is as large as possible. In particular, we consider OAs where the ratio is as large as possible; these OAs are termed optimal. We provide constructions of optimal OAs for any , albeit with large . We also study basic OAs; these are optimal OAs in which . We construct a basic OA with and , provided that a Hadamard matrix of order exists. This completely solves the problem of constructing basic OAs with , modulo the Hadamard matrix conjecture. 相似文献
15.
The paper deals with panchromatic 3-colorings of random hypergraphs. A vertex 3-coloring is said to be panchromatic for a hypergraph if every color can be found on every edge. Let denote the binomial model of a random -uniform hypergraph on vertices. For given fixed , and , we prove that if then admits a panchromatic 3-coloring with probability tending to 1 as , but if is large enough and then does not admit a panchromatic 3-coloring with probability tending to 1 as . 相似文献
16.
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. 相似文献
17.
A graph is -colorable if it admits a vertex partition into a graph with maximum degree at most and a graph with maximum degree at most . We show that every -free planar graph is -colorable. We also show that deciding whether a -free planar graph is -colorable is NP-complete. 相似文献
18.
19.
20.
For a positive integer , a graph is -knitted if for each subset of vertices, and every partition of into (disjoint) parts for some , one can find disjoint connected subgraphs such that contains for each . In this article, we show that if the minimum degree of an -vertex graph is at least when , then is -knitted. The minimum degree is sharp. As a corollary, we obtain that -contraction-critical graphs are -connected. 相似文献