THE CONNECTED SIZE RAMSEY NUMBER FOR MATCHINGS
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 s...
Saved in:
| Main Author: | |
|---|---|
| Format: | Dissertations |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/36176 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | 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}.
|
|---|