Size Ramsey numbers involving stars

We calculate some size Ramsey numbers involving stars. For example we prove that for t ? k ? 2 and n sufficiently large the size Ramsey number.

$\text{r}{}_{\mathrm{n}}\text{(K}{}_{\mathrm{1,k}}\text{K}{}_{\mathrm{t}}\text{+}\text{K}{}_{\mathrm{n}}\text{=}\text{k(t?1)+1}\text{2}\text{+(k(t?1)+1)(n+k?1).}$

     

Ramsey numbers for all linear forests

An (n, j) linear forest L is the disjoint union of nontrivial paths, such that j of the paths have an odd number of vertices and the union has n vertices. For L, an (n₁.j₁) linear forest and l₂ an (n.j₁) linear forest, we show that

$\text{r(L}{}_1\text{,L}{}_2\text{) = max{n}{}_1\text{·(n}{}_2\text{?j}{}_2\text{)/2 ? 1, n}{}_2\text{+ (n}{}_1\text{? j}{}_1\text{)/2 ? 1}.}$

This answers in the affirmative a conjecture of Burr and Roberts.     

Minimal Degree and (k, m)-Pancyclic Ordered Graphs

Given positive integers k m n, a graph G of order n is (k, m)-pancyclic ordered if for any set of k vertices of G and any integer r with m r n, there is a cycle of length r encountering the k vertices in a specified order. Minimum degree conditions that imply a graph of sufficiently large order n is (k, m)-pancylic ordered are proved. Examples showing that these constraints are best possible are also provided.     

Some connected ramsey numbers

A graph G is co-connected if both G and its complement ? are connected and nontrivial. For two graphs A and B, the connected Ramsey number r_c(A, B) is the smallest integer n such that there exists a co-connected graph of order n, and if G is a co-connected graph on at least n vertices, then A ? G or B ? ?. If neither A or B contains a bridge, then it is known that r_c(A, B) = r(A, B), where r(A, B) denotes the usual Ramsey number of A and B. In this paper r_c(A, B) is calculated for some pairs (A, B) when r(A, B) is known and at least one of the graphs A or B has a bridge. In particular, r_c(A, B) is calculated for A a path and B either a cycle, star, or complete graph, and for A a star and B a complete graph.