INFINITE FAMILY OF RAMSEY MINIMAL GRAPHS FOR THE PAIR PATHS

• Main Author: Rahmadani, Desi
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/36067
• Institution: Institut Teknologi Bandung

The study of Ramsey theory became more popular since Erd¨os and Szekeres applied it in graph theory. Some problems arise from development of Ramsey theory i.e determination of Ramsey number, size Ramsey number and Ramsey-minimal graph. Let G and H be graphs. Notation F ! (G;H) means that any red-blue coloring of edges of F implies that F contains either a red subgraph G or a blue subgraph H. A graph F is Ramsey graph for a pair (G;H) if F ! (G;H). The graph F is a Ramsey (G;H)-minimal graph if F ! (G;H) but F ???? e 9 (G;H) for any e 2 E(F). The class of all Ramsey (G;H)-minimal graphs is denoted by R(G;H). The class R(G;H) is said to be finite or infinite if the set R(G;H) is infinite or finite, respectively. The research in this dissertation is a study of infinite classes R(G;H), where G and H are paths. The problem of determination or characterization of graphs in R(G;H) for any G and H is an interesting study, even though in general this is difficult to determine or characterize the graphs belonging to R(G;H), even for G and H are graphs small-order and simple-structure. Moreover, since R(P3; Pn), for 3 m n is infinite, then characterization is a harder work. The characterization of Ramsey minimal graphs for pair (P3; P3) has been obtained. However, characterization graphs in R(Pm; Pn), for 3 m < n is still open. In this dissertation, some sufficient conditions for Ramsey (P3; Pn) graphs and necessary conditions for Ramsey (P3; Pn)-minimal graphs are derived. One of necessary condition states that the graphs inR(Pm; Pn) must be connected. Besides that, we give some properties for trees and unicyclic graphs in R(P3; Pn). Then, we construct some infinite families of trees and unicyclic graphs containing a cycle of length three until infinite in R(P3; Pn), for some n 4. For the remaining n 4, the infinite families of trees and unicyclic graphs are constructed by a recursive algorithm. Furthermore, we give some observations to determine unicyclic graphs obtained from trees in R(P3; Pn) by attaching two vertices. In this dissertation, we also give some properties for the graphs in R(P4; Pn). First, we show that the graphs must be connected and contains at least one cycle. By these properties, we first determine an infinite family of unicyclic graphs in R(P4; P4). Furthermore, we show that the uniqueness of these unicyclic graphs. Then, we iii determine some infinite families in R(P4; P4) containing more than one cycle. We also characterize all graphs of five and six orders belonging to R(P4; P4). Then, we show that all graphs in R(P4; Pn) for n 5 must contains at least two cycles, however the problem of determination the graphs in this class is still open. This problem is much more difficult because there are many possibilities of red-blue colorings that avoid a red P4 and a blue Pn, for some n 5.