RAMSEY MINIMAL GRAPH FOR PAIR OF GRAPHS CONTAINING CYCLES

• Main Author: Nabila, Maya
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/52455
• Institution: Institut Teknologi Bandung

A scientist named as Frank Plumpton Ramsey introduced a theory called as Ramsey theory to let us kow which logic formula that is correct or incorrect [24]. Then, the theory developes until we discovered Ramsey minimal graph theory that was introduced by Burr in 1970. Burr [7] defined the definition of Ramsey minimal graph theory as follows. Let G and H be any simple graph, it means not containing multiple edges and looping. Notation of F ! (G,H) means for any red-blue coloring to every edges in graph F we will always get a red copy of subgraph G or a blue copy of subgraph H. Then, 8e 2 F notation F ?e 9 (G,H) imply there is coloration to the edges of graph F ?e so that graph F ?e contains no red copy of subgraph G and blue copy of subgraph H. Class R(G,H) imply a set of graph that fulfill this two following conditions : 1. F ! (G,H) 2. 8e 2 F, F ? e 9 (G,H) Pair of (G,H)-minimal called as a finite Ramsey if class R(G,H) has finite elements, while pair of (G,H)-minimal called as an infinite Ramsey if class R(G,H) has infinite elements In this thesis, we will discuss some graphs that belong to the class R(G,H) with G is a cycle graph andH is a star graph. The problem of characterizing and determine all Ramsey (G,H)-minimal graphs for any graph G and H is not simple or easy to work with. We obtained some graphs of members of class Ramsey (Cn,K1,2)- minimal for n 2 [5, 9] and class Ramsey (C4,K1,m)-minimal for m % 3. Then, we already characterize a Ramsey (C2n,K1,2) graph for n % 7 odd number.