On Ramsey (mK2,bPn)-minimal Graphs

Abstract

Let G and H be two given graphs. The notation F→(G,H) means that any red-blue coloring on the edges of F will create either a red subgraph G or a blue subgraph H in F. A graph F is a Ramsey (G,H)-minimal graph if F satisfies two conditions: (1) F→(G,H), and (2) (F−e) ⇸ (G,H) for every e ∈ E(F). Denote ℜ(G,H) as the set of all (G,H)-minimal graphs. In this paper we prove that a tree T is not in ℜ(mK₂,bP_n) if it has a diameter of at least n(b+m−1)−1 for m,n,b≥2, furthermore we show that (b+m−1)P_n ∈ ℜ(mK₂,bP_n) for every m,n,b≥2. We also prove that for n≥3, a cycle on k vertices is in ℜ(mK₂,bP_n) if and only if k ∈ [n(b+m−2)+1, n(b+m−1)−1].