BILANGAN RAMSEY UNTUK GRAF RODA - Surahmat
Abstract: Ramsey theory was initially studied in the context of the problem of finding a regular procedure to determine the consistency of any given logical formula (1928). Then, this theory becomes famous after Paul Erdos and George Szekeres (1935) applied it in graph theory. The idea behind the classical Ramsey number is basically the following. For any positive integers a and b, we would like to determine the smallest integer R = R(a, b) so that every graph F of R vertices will satisfy the following condition: either F has Ka as a subgraph or the complement of F has Kb as a subgraph. The research on finding the exact value of classical Ramsey numbers R(a, b) has received a lot of attention. However, the results are still far from satisfactory. Since firstly introduced, there are only nine exact Ramsey numbers known so far. Next, the study of the classical Ramsey number has been generalized in various forms. One of them is called graph Ramsey numbers. The study of graph Ramsey numbers has grown enormously in the last four decades to become presently one of the most active areas in Ramsey theory. A mayor impetus behind the early development of graph Ramsey number was the hope that it would eventually leads to methods for determining larger value of the classical Ramsey numbers R(a, b). However, as often happens in mathematics, this hope has not been realized; rather, the field has blossomed into a discipline of its own. Let G and H be two graphs. Basically, the graph Ramsey number R(G, H) is defined as the smallest integer N such that every graph F of order N will satisfy the following condition: either F has G as a subgraph or the complement of F has H as a subgraph. In this dissertation, we shall study on the determination of graph Ramsey numbers R(G, Wm) for some fixed G and a wheel W,n of (m + 1) vertices. In particular, we consider G as a path Pn, a star Sn, a tree Tr), a star-like a linear forest Lp or a cycle Cn. In order to obtain the graph Ramsey number R(G, Wm), we firstly determine the lower bound by using the Chvatal and Harary's theorem (1972). However,in some cases, the lower bound given by Chvatal and Harary's theorem is not good enough. So, we have to increase the lower bound by finding corresponding (G, Wm)-good graphs. To find the graph Ramsey numbers, we have to show that the upper bound coincide with the lower bound. In most cases, we use the induction process. The main results of the dissertation are in the following. We show that R(Pn, Wm) = 2n - 1 for m even and n > m > 4, and R(Pn, Wm) = 3n - 2 for m even and n > m> 3. For a star Sn, we obtain the graph Ramsey numbers R(ST, W4) = 2n - 1 for n odd and n > 3; R(Sn, W4) = 2n+1 for n even and n > 4, R(Sn, W5) = 3n-2 for n > 3. In general, we show that R(Sn, Wm) = 3n - 2 for in odd, in > 5 and n > 2m - 4. If G is a tree TT, other than a star, then we obtain the graph Ramsey number R(Tn, W4) = 2n - 1 for n > 4, and R(Tn, W5) = 3n - 2 for n > 3. For particular form of trees, we also obtain the graph Ramsey number R(Tn, Wm) for in odd, in > 5 and n > 2m - 4 where TT, is a star-like. We are able to obtain the graph Ramsey numbers R(Lp, Wm) where Lp is a linear forest and m odd, m > 5 and n > 2m - 4. Our final result concerns with the finding of R(Cn, Wm). We show that R(C4, W4) = 9, R(C4, W5) = 10, R(C4, W6) = 9, R(Cn, W4) = 2n - 1 for n > 5, and R(Cn, W5) = 3n - 2 for n > 5.