RAMSEY MINIMAL GRAPHS FOR PAIR OF CYCLE AND STAR GRAPHS

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

Frank Plumpton Ramsey introduced the Ramsey theory, which enables us to determine whether a logic formula is correct or incorrect (Ramsey, 1930). Then, this theory was developed and studied in various variants along with the generalization. One of the generalizations is the Ramsey minimal graph that was introduced by Burr et al. (1976). Let G and H be any simple graphs. The notation F ! (G,H) implies that for any red-blue coloring on the edges of F, there exists a red copy of a subgraph G or a blue copy of a subgraph H. Then, for every edge e 2 E(F), the notation F ? e 9 (G,H) implies that there is a red-blue coloring on the edges of F ? e such that the graph F ?e contains no red copy of a subgraph G and no blue copy of a subgraph H. A class R(G,H) is a set of graphs that fulfills these two following conditions : (i) F ! (G,H) and (ii) for any e 2 F, F ? e 9 (G,H). A pair of (G,H) is called finite Ramsey if the class R(G,H) has finite elements, while a pair of (G,H)-minimal is called infinite Ramsey if the class R(G,H) has infinite elements. The research in this dissertation is a study of the infinite class R(G,H), where G is a cycle and H is a star. The problem of characterizing and determining all of the Ramsey (G,H)-minimal graphs for any G and H is not simple or easy work to do, even for G and H that are in small-order and simple-structure graphs. But this problem is still an interesting problem to study. Some Ramsey minimal graphs in the classesR(C3,K1,2),R(C4,K1,2), orR(C6,K1,2) have been obtained. However, in general, the characterization graphs in R(Cm,K1,n) for any m $ 3 and n $ 2 are still an open problem. The results in this dissertation can be divided into two parts, namely the Ramsey graph (Cm,K1,2)-minimal for m $ 7 and the Ramsey graph (C4,K1,n) for n $ 2. In the first part, the results are the Ramsey graph (C2m,K1,2) for m $ 6, which is constructed by modifying the Harary graph, and the Ramsey graph (Cm,K1,2) which is obtained from a certain class of circulant graphs for m $ 7. For m 2 {8, 9, 10} and m = 4k + 3, with k a positive integer, it can be shown that the class of circulant graphs is the Ramsey graph (Cm,K1,2)-minimum. The main result in the second part is a method of Ramsey minimal graph construction called the theta-F graph. The theta-F graph is constructed by any edge-weighted graph F. We obtain the sufficient and necessary conditions regarding the sum of the edge weights of F such that the theta-F graph is a Ramsey graph (C4,K1,n)-minimal. In addition, we derive the properties of the distribution of edge weights and vertex weights in the graph F. The vertex weight is the sum of the edge weights incident to that vertex. The construction method mentioned above is extended by incorporating subdivision operations on F. By doing subdivision operations repeatedly, we obtain an infinite class of theta-graphs in R(C4,K1,n) for n $ 2. Based on the conditions for vertex and edge weights, several sequences of edge weights for tree and unicyclic graphs are also given to obtain theta-trees and theta-unicyclic, which are members of the class R(C4,K1,n). For an additional result, we give the construction of a new class of graphs called H(n) graphs, which are (C4,K1,n)-minimal Ramsey graphs for every n $ 3.