RAMSEY (P3; P6)-MINIMAL GRAPHS

• Main Author: Rahmadani, Desi
• Format: Theses
• Language: Indonesia
• Subjects: Matematika
• Online Access: https://digilib.itb.ac.id/gdl/view/33604
• Institution: Institut Teknologi Bandung

Let F, G and H be graphs. The notation F !(G;H) means that any red-blue coloring of the edges of F contains a red subgraph G or a blue subgraph H. Graph F is called a Ramsey (G;H)-minimal graph if it satisfies that F !(G;H) and F - e ->(G;H) for any e 2 E(F). The notation R(G;H) is the set of all Ramsey (G;H)-minimal graphs. In this thesis, we determine some Ramsey (P3; P6)-minimal graphs of order at most 11 and characterize all such Ramsey minimal graphs of order 6 by using their degree sequences. We determine some class graphs which belongs to Ramsey (P3; Pn)-minimal, n - 6 and construct an infinite class of trees which provides Ramsey (P3; P6)-minimal graphs. We also show that the maximum degree of such a tree is three and the lower bound of diameter of graphs which belongs to R(P3; P6) is two.