THE CONNECTED SIZE RAMSEY NUMBER FOR MATCHINGS

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

Given graphs G and H, the notation F?(G,H) means that in any red-blue coloring of the edges of F there exists a red subgraph G or a blue subgraph H in F. The size Ramsey number of a pair of graphs G and H, denoted by r ?(G,H), is the smallest integer k such that there is a graph F with k edges satisfying F?(G,H). In general, the smallest graph F satisfying F?(G,H) is not necessarily connected. In accordance with connectedness, we define the connected size Ramsey number of graphs G and H, denoted by r ?_c (G,H) as the smallest integer t such that there is a connected graph F with t edges satisfying F?(G,H). In this dissertation, we focus on the study of connected size Ramsey numbers involving matching r ?_c (?nK?_2,H), where H are some classes of connected or disconnected graphs. First, we determine the connected size Ramsey number r ?_c (?nK?_2,H), where H is a star, a path, a double star, a broom, or a cycle. Moreover, we also determine the connected size Ramsey number r ?_c (?nK?_2,H), where H is a matching, a union of stars, or a union of paths. In the study the connected size Ramsey number r ?_c (?nK?_2,H), where H is a star or a path, we derive an upper bound of r ?_c (?nK?_2,K_(1,m) ) and r ?_c (?nK?_2,P_t ) for n?2, m?3, and t?3. Then, we determine the exact values of r ?_c (?nK?_2,K_1,3 ) for n?2, r ?_c (?nK?_2,K_(1,m) ) for n?{2,3},m?4, and r ?_c (?nK?_2,P_t ) for t?{3,4,5} and n?{3,4,5,6}. For the connected size Ramsey number r ?_c (?nK?_2,H), where H is a cycle, a double star, or a broom, we derive an upper bound of r ?_c (?2K?_2,C_r ) for r?7, r ?_c (?nK?_2,C_4 ) for n?4, r ?_c (?2K?_2,S(1,m)) for m?3, r ?_c (?2K?_2,S_(m,m) ), and r ?_c (?3K?_2,S_(m,m) ) for m?2. Moreover, we obtain the exact values of r ?_c (?nK?_2,C_r ) for n?{2,3} and t?{4,5,6},? r ??_c (?2K?_2,S_(m,m) ) for m?{2,3}, and r ?_c (?2K?_2,S(1,m)) for m?3. Finally, we determine an upper bound of r ?_c (?nK?_2,?2P?_3 ) for n?2. Then, we also present the exact value of the connected size Ramsey number r ?_c (?nK?_2,?lK?_2 ), r ?_c (?nK?_2,?2K?_(1,m) ), and r ?_c (?nK?_2,?2P?_t ) for n,l,t?2, m?3. Moreover, we obtain r ?_c (?nK?_2,?2P?_3 ) for n?{3,4,…,8}.