Asymptotic upper bounds for wheel:complete graph Ramsey numbers

It is shown that r(W_m, K_n)≤(1+o(1))C_1n log n 2m-2m-2 for fixed even m≥4 and n→∞, and r(W_m, K_n)≤(1+o(1))C_2n 2mm+1 log n m+1m-1 for fixed odd m≥5 and n→∞, where C_1=C_1(m)>0 and C_2=C_2(m)>0, in particular, C_2=12 if m=5 . It is obtained by the analytic method and using the function f_m(x)=∫ 1 _ 0 (1-t) 1m dtm+(x-m)t , x≥0 , m≥1 on the base of the asymptotic upper bounds for r(C_m, K_n) which were given by Caro, et al. Also, cn log n 52 ≤r(K_4, K_n)≤(1+o(1)) n 3 ( log n) 2 (as n→∞ ). Moreover, we give r(K_k+C_m, K_n)≤(1+o(1))C_5(m)n log n k+mm-2 for fixed even m≥4 and r(K_k+C_m, K_n)≤(1+o(1))C_6(m)n 2+(k+1)(m-1)2+k(m-1) log n k+2m-1 for fixed odd m≥3 (as n→∞ ).

Ramsey numbers r(K_(1, 4), G) for all three-partite graphs G of order six

In this paper, we use a combinatorial analysis method. In the complete graph K N with edges colored arbitrarily by red or blue, we consider the proposition of the subgraph of the red graph or blue graph induced by the neighborhood of some vertex in V(K N). Inspired by the main results of Jayawardene and Rousseau (Ars Combinatoria, 2000, 163-173), we determine the Ramsey numbers of r(K 1, 4, G), where G is the three-partite graph of order six without isolate vertex.

Upper Bounds for Ramsey Numbers R(m,n,l) and R(m,n,l,s) with Parameter

In the paper some new upper bounds with parameters were obtained for the classical Ramsey numbers R(m,n,l) and R(m,n,l,s) . By using the upper bounds, it was proved that R (4,4,4)≤236.

Ramsey Numbers of Trees Versus Multiple Copies of Books

Given two graphs G and H,the Ramsey number R(G,H) is the minimum integer N such that any two-coloring of the edges of K_(N) in red or blue yields a red G or a blue H.Let v(G) be the number of vertices of G and χ(G) be the chromatic number of G.Let s(G) denote the chromatic surplus of G,the number of vertices in a minimum color class among all proper χ(G)-colorings of G.Burr showed that R(G,H)≥(v(G)-1)(χ(H)-1)+s(H) if G is connected and v(G)≥s(H).A connected graph G is H-good if R(G,H)=(v(G)-1)(χ(H)-1)+s(H).Let tH denote the disjoint union of t copies of graph H,and let G∨H denote the join of G and H.Denote a complete graph on n vertices by K_(n),and a tree on n vertices by T_(n).Denote a book with n pages by B_(n),i.e.,the join K_(2) ∨■.Erd?s,Faudree,Rousseau and Schelp proved that T_(n) is B_(m)-good if n≥3m-3.In this paper,we obtain the exact Ramsey number of T_(n) versus 2B_(2).Our result implies that T_(n) is 2B_(2)-good if n≥5.

Multicolored Bipartite Ramsey Numbers of Large Cycles

For an integer r≥2 and bipartite graphs Hi,where 1≤i≤r,the bipartite Ramsey number br(H1,H2,…,Hr)is the minimum integer N such that any r-edge coloring of the complete bipartite graph KN;N contains a monochromatic subgraph isomorphic to Hi in color i for some 1≤i≤r.We show that if r≥3;α1,α2>0,αj+2≥[(j+2)!-1]Σi=1^(j+1)α1 for j=1,2…r-2,then br(C2[α1n],C2[α2n],…,C2[αrn]=(Σ=j=1^(r)a j+o(1))n.

Star-critical Ramsey Numbers of Wheels Versus Odd Cycles

Let K_(1,k)be a star of order k+1 and K_(n)■K_(1,k)the graph obtained from a complete graph K_(n)and an additional vertex v by joining v to k vertices of K_(n).For graphs G and H,the star-critical Ramsey number r_(*)(G,H)is the minimum integer k such that any red/blue edge-coloring of K_(r-1)■K_(1,k)contains a red copy of G or a blue copy of H,where r is the classical Ramsey number R(G,H).Let C_(m)denote a cycle of order m and W_(n)a wheel of order n+1.Hook(2010)proved that r_(*)(W_(n),C_3)=n+3 for n≥6.In this paper,we show that r_(*)(W_(n),C_(m))=n+3 for m odd,m≥5 and n≥3(m-1)/2+2.

THE RAMSEY NUMBERS R(T_n, W_6) FOR T_N WITHOUT CERTAIN DELETABLE SETS

Let Tn denote a tree of order n and Wm a wheel of order m+1. In this paper,we determine the Ramsey numbers R(Tn W6) for Tn without certain deletable sets.

THE BOUNDS ABOUT THE WHEEL-WHEEL RAMSEY NUMBERS

In this paper, we determine the bounds about Ramsey number R（Wm, Wn）, where Wi is a graph obtained from a cycle Ci and an additional vertex by joining it to every vertex of the cycle Ci. We prove that 3m＋ 1 ≤ R（Wm, Wn） ≤ 8m-3for odd n, m≥n≥3, m≥5, and2m＋1≤R（Wm, Wn） 〈7m-2 for even n and m ≥ n ＋ 502. Especially, if m is sufficiently large and n = 3, we have R（Wm, W3） = 3m ＋ 1.

Ramsey Number of K_(2,s+1) vs.K_(1,n)

It is shown that the Ramsey number r（K2,s＋1,K1,n）≤n＋√sn＋（s＋3）/2＋o（1）for large n, and r（K2,s＋1, K1,n） ∈{（q-1）^2/s ＋ 1,（q-1）^2/s＋2},where n =（q-1）^2/s -q＋2 and q is a prime power such that s｜（q - 1）.

A Way Finding the Classical Ramsey Number and r（4,6）=36

Two definitions are given that Definitionl： an induced subgraph by a vertex vie G and its neighbors in G is defined as a vertex adjacent closed subgraph, and denoted by Qi （=G[V（Nvi）]）, with the vertex vi called the hub; and Definition2： A r（k,I）-I vertices graph is called the （k,l）-Ramsey graph, denoted by RG（k,1）, if RG（k,1） only contains cliques Kk.1 and the intersect QiNQj of any two nonadjacent vertices vi and vj of RG（k,I） contains only Kk-2. Meanwhile, the RG（k,l）＇s complement RG（I,k） contains only cliques Kl.l, and the intersect QiNQj of any two nonadjacent vertices vi and vj of RG（I,k） contains only Ki.2. On the basis of those definitions, two theorems are put forward and proved in this paper. They are Theoreml： the biggest clique in G is contained in some Qi of G, and Theorem 2： r（k,1） = [V（RG（k,I））I ＋ 1. With those definitions and theorems as well as analysis of chord property, a method for quick inspection and building RG（k,1） is proposed. Accordingly, RG（4,6） is built, it is a strongly 14-regular graph on order 35. We have tested RG（4,6） and its complement, as a result, they meet the defintion2, so we proclaim that r（4,6）=36.

An Application of the Ramsey Number in the Electricity Pricing

The Ramsey number is a foundational result in combinatorics. This article will introduce Ramsey number with the method of graph theory, and the Ramsey pricing theory is applied to the sales price and study of cross subsidy. Based on the status of our sales price and cross subsidy, Ramsey pricing methods theoretically guide adjustment thoughts of sales price and solve the practical problems in our life.

The <i>H</i>-Decomposition Problem for Graphs

The concept of H-decompositions of graphs was first introduced by Erd?s, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Ф(n,H) be the smallest number Ф, such that, any graph of order n admits an H-decomposition with at most Ф parts. The exact computation of Ф(n,H) for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decom- positions of graphs.

A way finding r（k,I） and r（3,10）=41

On basis of two definitions that 1. an induced subgraph by a vertex vi E G and its neighbors in G is defined a vertex adjacent closed subgraph denoted by Qi （=G[V（Nvi）]）, with the vertex vi called the hub; 2. A r（k,1）-1 vertices connected graph is called a （k,l）-Ramsey graph denoted by RG（k,l）,if and only if 1. RG（k,l） contains only cliques of degree k-1, and its complement contains only cliques of degree l-l; 2. the intersect Qi∩Qj of any two nonadjacent vertices vi and vj of RG（k,1） contains Kk.2, and the intersect Qi∩Qj of any two nonadjacent vertices vi and vj of its complement RG（l,k） contains KI.2. Two theorems that theoreml ： the biggest clique in G is contained in some Qi of G, and theorem2： r（k,l）= [ V（RG（k,I）） I ＋1 are put forward and proved in this paper. With those definitions and theorems as well as analysis of property of chords a method for quick inspection and building RG（k,I） is proposed. Accordingly, RG（10,3） and its complement are built, which are respectively the strongly 29-regular graph and the strongly 10-regular graph on orders 40. We have tested RG（10,3） and its complement RG（3,10）,and gotten r（3,10）=41.

The lower bounds of classic Ramsey number R(5,9). and R (5,10)

IT is very difficult to establish the Ramsey number, so we often use the way of getting the up-per and lower bound of the Ramsey number to near the exact value. All lower bounds of R (5,l) known so far are shown in table 1.

Lower Bounds of Size Ramsey Number for Graphs with Small Independence Number

Let r≥3 be an integer such that r−2 is a prime power and let H be a connected graph on n vertices with average degree at least d andα(H)≤βn,where 0<β<1 is a constant.We prove that the size Ramsey number R^(H;r)>nd2(r−2)2−Cn−−√for all sufficiently large n,where C is a constant depending only on r,d andβ.In particular,for integers k≥1,and r≥3 such that r−2 is a prime power,we have that there exists a constant C depending only on r and k such that R^(Pkn;r)>kn(r−2)2−Cn−−√−(k2+k)2(r−2)2 for all sufficiently large n,where P k n is the kth power of Pn.

RAMSEY NUMBER OF HYPERGRAPH PATHS

Let H =(V, E) be a k-uniform hypergraph. For 1 ≤ s ≤ k-1, an s-path P^(k,s)_n of length n in H is a sequence of distinct vertices v_1, v_2, · · ·, v_(s+n(k-s)) such that {v_(1+i(k-s)), · · ·, v_(s+(i+1)(k-s))} is an edge of H for each 0 ≤ i ≤ n-1.In this paper, we prove that R(P^(3 s,s)_n, P^(3 s,s)_3) =(2 n + 1)s + 1 for n ≥ 3.