ON RAMSEY (P3;C5)-MINIMAL GRAPHS

• Main Author: AHSANUNNISA, MARYAM
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/18886
• Institution: Institut Teknologi Bandung

Let G and H be two given graphs. The notation F !(G;H) means that every red-blue coloring on the edges of F satisfies the following condition: F contains either a red subgraph G or a blue subgraph H. A graph F is a Ramsey (G;H)- minimal graph if F ! (G;H) but F 9 (G;H) for any proper subgraph F of F. Let Â(G;H) be the set of all Ramsey (G;H)-minimal graph. In 1975, Burr et al. emerge question about characteristics of all graphs F in Â(G;H). Burr et al. (1976) showed that infinite set of Â(K1;2;K1;2) = fK1;3g [ fC2n+1jn 1g. Then, in 1978, Burr et al. proved that finite set of Â(2K2;2K2) = f3K2;C5g. Borowiecki et al. also succeeded characterizing all graphs that included in an infinite set of Â(K1;2;K1;m) for m3 in 2004, followed by characterization all graphs in a finite set of Â(K1;2;K1;3) in 2005. Whether the set of Â(G:H) is finite of not, depended upon the pairs of (G;H). Burr et al. (1980) proved that if H is a 2- connected graph, Â(K1;2;H) is infinite class for k 2. Yulianti (2011) inspects the way to determine the elements of infinite class Â(K1;2;C4) and Â(K1;2;Cn) for n 4, and then gave some unsolved problems, one of them was graphs characterization of members of Â(K1;2;Cn) untuk n 4. Then, Baskoro et al. (2008) gave some members of Â(K1;2;C4) and an unsolved problem which was determination of all graph members of Â(K1;2;C4) with diameter 2 and 3. Thereafter, Baskoro et al. (2008) gave some new graph members of Â(K1;2;C4) with diameter 2. And then, Vetr´?k et al. gave all graphs in Â(K1;2;C4) that have diameter 4. In this final project, we will investigate the properties of the graphs in Â(P3;C5). Based on these properties, we determine some graphs in Â(P3;C5).