On Ramsey (K1,m,G)(K1,m,G)-minimal graphs

Let FF be a graph and let GG, HH denote nonempty families of graphs. We write F→(G,H)F→(G,H) if in any 22-colouring of edges of  FF with red and blue, there is a red subgraph isomorphic to some graph from GG or a blue subgraph isomorphic to some graph from HH. The graph FF without isolated vertices is said to be a  (G,H)(G,H)-minimal graph if F→(G,H)F→(G,H) and F−e⁄→(G,H)F−e⁄→(G,H) for every e∈E(F)e∈E(F). The set of all (G,H)(G,H)-minimal graphs (up to isomorphism) is called the Ramsey set ℜ(G,H)ℜ(G,H).We present a procedure, which on the basis of the set of some special graphs, generates an infinite family of  (K1,m,G)(K1,m,G)-minimal graphs, where m≥2m≥2 and GG is a family of 2-connected graphs. Moreover, graphs obtained by this procedure can be obtained in linear time with respect to their order. In particular, we present how to obtain infinitely many graphs from Ramsey sets ℜ(K1,m,Kn)ℜ(K1,m,Kn), ℜ(K1,m,Kp,q)ℜ(K1,m,Kp,q), for every m,p,q≥2m,p,q≥2 and n≥3n≥3, and from Ramsey sets ℜ(K1,m,Cn)ℜ(K1,m,Cn), for m≥2m≥2 and n∈[4,6]n∈[4,6]. We show minimal graphs with respect to the number of vertices, which belong to the family ℜ(K1,m,Kn)ℜ(K1,m,Kn), for m,n≥3m,n≥3. We also present graphs which can be used to the construction of infinitely many graphs belonging to the Ramsey set ℜ(K1,m,G)ℜ(K1,m,G), where m≥2m≥2 and GG is some family of 2-connected graphs consisting of more than one graph.