| There are many applications of Ramsey theory in mathematics, computer science, information theory, and decision science. To determininc the exact values of graph Ramsey numbers is an important cross field of Ramsey theory and graph theory. Graph Ramsey numbers have many applications in computer science, such as logic, parallel computation, and computational geometry. By the methods combining computer construction and mathematical proofs, the star-critical Ramsey numbers involving cycles, Ramsey numbers of quadrilateral versus wheels (or stars), and Ramsey numbers of cycle-sets versus complete graphs are studied in this dissertation.Star-critical Ramsey numbers of quadrilateral versus cycles r*(C4, Cn). The concept of star-critical Ramsey numbers was introduced by Hook and Isaak in 2011, and the exact value of r*(C4, C3) is given. In this paper, by using Hamilton properties of graph, the structures of all (C4, Cn;n)-graphs are proved. Then utilizing the Hamilton-connected characteristics of three kinds of graphs, the maximum number of edges can be added is analyzed between a new vertice v and n vertices of a (C4, Cn, n)-graph. Finally, the results that r*(C4, Cn)= 5 for n≥4 are proved.Ramsey numbers of quadrilateral versus wheels R(C4, Wm). Tse determined the exact values of R(C4, Wm) for 7≤m≤13. Dybizbanski and Dzido proved that R(C4, Wm) =m+4 for 14< m< 17, and gave an upper bound on R(C4, Wm) for m≥11. First, by studying the structures of (k,5)-cages for 3≤k≤7, the graphs that do not contain C4 and have the minimum degrees satisfied the specified requirements are constructed, then several lower bounds on R(C4, Wm) are proved. Secondly, the necessary and sufficient condition of G being a (C4, Wm;n)-graph is proved, and by utilizing the known results of extremal graphs without C4, several upper bounds on R(C4, Wm) are improved. Finally, the exact values of R(C4,Wm) for 9 cases of n between 18 and 44 are determined.Ramsey numbers of quadrilateral versus stars (or wheels). For Ramsey numbers of quadrilateral versus stars R(C4,K1,m), Parsons gave their upper bounds and proved that R(C4, K1,q2)= q2+q+1 and R(C4, K1.q2+1)= q2+q+2 for prime powers q. In this dissertation, by studying the structures of polarity graphs from a projective plane, the lower bounds on R(C4, K1,q2-2) for prime powers q are obtained. Then by utilizing the known upper bounds on R(C4, K1,q2-2), the results that R(C4,K1,q2-)= q2+q-1 are proved, where q being a prime power. Using the similar method, the lower bounds on R(C4, Wq2+2) and R(C4, q2-1) for prime powers q are given. By analyzing the characteristics of graphs of order q2+q+2 without C4 in detail, the upper bounds on R(C4, ) are further improved. Then, with the known results of the upper bounds on R(C4, ), it is proved that R(C4, Wq2+2)=q2+q+2,and R(C4,Wq2-1)=q2+q-1 for prime powers q.Ramsey numbers of cycle-sets versus complete graphs R(C≤m, Km). Erdos et al. proved that R(C≤n, Km)=2m-1 for n≥2m-1, and R(C≤n,Km)= 2m for m<n<2m-1. First, the structures of all graphs in EX(2n; C≤n,) are proved by using characteristics of plane graphs in this dissertation, and by studying the independence numbers of graphs in EX(2n; C≤n), it is proved that R(C≤n,Kn)= 2n for odd n, and R(C≤n, Kn)= 2n+1 for even n. Secondly, based on the conclusions above, the upper bounds on R(C≤n, Kn+1) are determined, and by constructing (C≤n, Kn+1;2n+2)-graphs, the results that R(C≤n,, Kn+1)= 2n+3 for odd n≥4 and even n≥16 are proved. Finally, the lower bounds on R(C≤n, Kn+2) are given by constructing (C≤n, Kn+2;2n+4)-graphs, then by the proof of the structures of all (C≤n, Kn+1;2n+2)-graphs, the upper bounds on R(C≤n, Kn+2) for odd n≥ 25 are obtained, the results that R(C≤n, Kn+2)= 2n+5 for odd n≥25 are proved.The multi-core algorithm for computing Ramsey numbers R (C≤m,Km). First, the single-core algorithm for computing Ramsey numbers of cycle-sets versus complete graphs is designed. Then, by analyzing the part of this algorithm which can be processed in parallel, the multi-core parallel algorithm is designed and implemented based on Phoenix++. By mapping the key-value pairs properly, preprocessing the data effectively and dividing the datasets evenly, the efficiency of the algorithm is substantially improved. Finally, employing the parallel algorithm, the exact values of R(C≤n,Kn+1) and R(C≤n, Kn+2) for 4≤n≤12 are obtained. |
