RESTRICTED SIZE RAMSEY NUMBER INVOLVING GRAPH OF SIZE TWO

• Main Author: RIAMA SILABAN - NIM: 30114001 , DENNY
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/26495
• Institution: Institut Teknologi Bandung

<p align="justify">The (restricted) size Ramsey number is an interesting problem in Ramsey theory. This field is still open to be explored. <br /> <br /> <br /> The size Ramsey number of a pair of graphs G and H, r &#770;(G,H), is the smallest number of edges in graph F such that for any 2-coloring of the edges of F we have a monochromatic G or H. If the order of F equals to r(G,H) with the property for any 2-coloring of the edges of F we have a monochromatic G or H, then the smallest number of edges in F is called the restricted size Ramsey number of G and H, denoted by r^* (G,H). The Ramsey number of a pair of graphs G and H, r(G,H), is the smallest number of vertices in F such that for any 2-coloring of the edges of F we have a monochromatic G or H. It is obvious that r &#770;(G,H)&#8804;r^* (G,H) and r^* (G,H) is also bounded above by the size of complete graph of order r(G,H). It is also known that both r &#770;(G,H) and r^* (G,H) are bounded below by e(G)+e(H)-1, with e(G) denotes the size of graph G. <br /> <br /> <br /> There are two fundamental questions related to the size Ramsey number of a pair of graphs. First, is there any pair of graphs G and H such that r &#770;(G,H) attaining the above upper bound? Second, do we have a pair of graphs G and H such that r &#770;(G,H) is significantly different from the upper bound? These two questions are also applicable to the restricted size Ramsey number of graphs. <br /> <br /> <br /> In this dissertation, we focus on the study of (restricted) size Ramsey number r &#770;(G,H) and r^* (G,H) where G is a graph of size two, namely G&#8773;P_3 or G&#8773;2K_2. To answer the first question, we give the necessary and sufficient conditions for a graph H such that r^* (P_3,H) attaining the upper bound. We also derive such conditions for r^* (2K_2,H). To answer the second question, we give the necessary and sufficient conditions for a graph H such that r^* (P_3,H) attaining the lower bound. While, for r^* (2K_2,H), we show that there is no graph H satisfying this condition. <br /> <br /> <br /> Furthermore, we determine r^* (P_3,H) for a dense graph H. In particular, we consider graphs H of order n that containing a complete graph of n-1 and n-2 vertices. Meanwhile, we determine r^* (2K_2,H) for some graph H where r &#770;(2K_2,H) has been known. The graphs H are star, star with one additional edge, and complete bipartite. <br /> <br /> <br /> Moreover, we consider a sparse graph. We determine r^* (P_3,H) for H are path and cycle. In this case, we obtain only the lower and upper bounds of r^* (P_3,H). The exact values are given just for a few small paths and cycles. For r^* (2K_2,H), we derive the exact value when H is a path. We also show that for H is a path, it satisfies r &#770;(2K_2,H)=r^* (2K_2,H). <br /> <br /> <br /> Additionally, we give r^* (P_3,H) and r^* (2K_2,H) for H are small graph of order five and six. This result is a continuation of the known results for small-order graphs.<p align="justify"> <br />