On Ramsey (P_4, P_4) -minimal graphs for small-order

摘要

We consider two simple graphs G and H, the notation F → (G,H) means that for any red-blue colouring of all the edges of F contains either a red copy isomorphic to G or a blue copy isomorphic to H. A graph F is a Ramsey (G,H)-minimal graph if F → (G,H) and for any edge e in F then {formula} (G,H). The application of this concept can be used in computer networks. The Ramsey (G,H) - minimal graphs can represent the arrangement of computer networks needed to keep several computers connected even though the network is given certain constraints. The set of all Ramsey minimal graphs for pair (G, H) is denoted by R(G, H). The Ramsey set for pair (G, H) is said to be Ramsey-finite or Ramsey-infinite if R(G,H) is finite or infinite, respectively. Several articles have discussed the problem of determining whether R(G,H) is finite or infinite. It is known that the set R(P_m, P_n), for 3 ≤m≤n is Ramsey-infinite. Some partial results in R(P_4, P_n), for any n > 4, have been obtained. However, the characterization of all graphs in the infinite set R(P_4, P_4) is still open. In this paper, we characterize all graphs of order five and six in R(P_4, P_4). In addition, we give a bicyclic graph in R(P_4, P_4). By a graph in R(P_4,P_4), we construct a graph in R(P_4,P_5).