RAMSEY (P3; P6)-MINIMAL GRAPHS
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Theses |
| Language: | Indonesia |
| Subjects: | |
| Online Access: | https://digilib.itb.ac.id/gdl/view/33604 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | 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. |
|---|