ON THE GRAPH RAMSEY NUMBER FOR A WHEEL: Dissertation abstract

• Main Author: Surahmat
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/5544
• Institution: Institut Teknologi Bandung

<b>Abstract: </b><p align=\"justify\"> 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 K_a as a subgraph or the complement of F has K_b as a subgraph.<p align=\"justify\"> The research on finding the exact value of classical Ramsey numbers R(a, b) has received a lot of attention. How-ever, the results are still far from satisfactory. Since firstly introduced, there are only nine exact Ramsey numbers known so far.<p align=\"justify\"> 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 be-come 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.<p align=\"justify\"> 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.<p align=\"justify\"> In this dissertation, we shall study on the determination of graph Ramsey numbers R(G, W_m) for some fixed G and a wheel W_m of (m + 1) vertices. In particular, we consider G as a path P_n, a star S_n, a tree T_n, a star-like Y_{n,l₁,...,l_k}, a linear forest L_p or a cycle C_n.<p align=\"justify\"> In order to obtain the graph Ramsey number R(G, W_m), we firstly determine the lower bound by using the Chvátal and Harary\'s theorem (1972). However, in some cases, the lower bound given by Chvátal and Harary\'s theorem is not good enough. So, we have to increase the lower bound by finding corresponding (G, W_m)—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.<p align=\"justify\"> The main results of the dissertation are in the following. We show that R(P_n, W<sub>m</Sub>) = 2n—1 form even and n &#8805; m &#8805; 4, and R(P_n, W_m) = 3n — 2 for m even and n &#8805; m &#8805; 3.<p align=\"justify\"> For a star S_n, we obtain the graph Ramsey numbers R(S_n, W₄) = 2n — 1 for n odd and n &#8805; 3; R(S_n, W₄) = 2n + 1 for n even and n &#8805; 4, R(S_n, W₅) = 3n—2 for n &#8805; 3. In general, we show that R(S_n, W_m) = 3n — 2 for m odd, m &#8805; 5 and n &#8805; 2m — 4.<p align=\"justify\"> If G is a tree T_n other than a star, then we obtain the graph Ramsey number R(T_n, W₄) = 2n — 1 for n &#8805; 4, and R(T_n, W₅) = 3n — 2 for n &#8805; 3. For particular form of trees, we also obtain the graph Ramsey number R(T_n, W_m) for m odd, m &#8805; 5 and n &#8805; 2m — 4 where TT, is a star-like. We are able to obtain the graph Ramsey numbers R(L_p, W_m) where L_p is a linear forest and m odd, m &#8805; 5 and n &#8805; 2m — 4.<p al ign=\"justify\"> Our final result concerns with the finding of R(C_n, W_m). We show that R(C₄, W₄) = 9, R(C₄, W₅) = 10, R(C₄, W₆) = 9, R(C_n,W₄) = 2n — 1 for n &#8805; 5, and R(C_n, W₅) = 3n — 2 for n &#8805; 5.