On Ramsey -minimal graphs

Let F be a graph and let G , H denote nonempty families of graphs. We write F → ( G,H ) if in any 2 -colouring of edges of  F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H . The graph F without isolated vertices is said to be a  ( G,H ) -minimal graph if F → ( G,H ) and F − e ⁄ → ( G,H ) for every e ∈ E ( F ) . The set of all ( G,H ) -minimal graphs (up to isomorphism) is called the Ramsey set ℜ ( G,H ) . sent a procedure, which on the basis of the set of some special graphs, generates an infinite family of  ( K 1 , m , G ) -minimal graphs, where m ≥ 2 and G 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 ℜ ( K 1 , m , K n ) , ℜ ( K 1 , m , K p , q ) , for every m , p , q ≥ 2 and n ≥ 3 , and from Ramsey sets ℜ ( K 1 , m , C n ) , for m ≥ 2 and n ∈ [ 4 , 6 ] . We show minimal graphs with respect to the number of vertices, which belong to the family ℜ ( K 1 , m , K n ) , for m , n ≥ 3 . We also present graphs which can be used to the construction of infinitely many graphs belonging to the Ramsey set ℜ ( K 1 , m , G ) , where m ≥ 2 and G is some family of 2-connected graphs consisting of more than one graph.