|
4 |
added graph theory tag
|
||
|
3 | deleted 2 characters in body | ||
|
A graph with number of vertices less than R(n,n)-1, is called quasi-Ramsey of case n, if it has no complete graph Kn in itself or its complementary graph, and if added another vertex, no matter how it is lined to the graph, the derived graph will have Kn in itself or its complementary. When the number of vertices is R(n,n)-1, called call it a Ramsey graph. There is a simple example to show the existence of quasi-Ramsey graph. First R(n,n)>(n-1)(n-1). Second, choose n-1 (n-1)-complete graphs Kn-1, without any lines between any two vertices from two distinct Kn-1. This graph with (n-1)(n-1) vertices is a quasi-Ramsey graph. Furthermore, there are a series of questions about it. For example, if there could be non-isomorphic quasi-Ramsey graphs with same number of vertices, if they are all completely symmetrical (vertex transitive)and how many quasi-Ramsey graphs there are. If all the quasi-Ramsey graphs can be cleared out, we will get a deeper understanding of the structure of Ramsey graphs. Then we are more likely to obtain better estimates of Ramsey numbers. |
||||
|
2 | added 10 characters in body | ||
|
A graph with number of vertices less than R(n,n)-1, is called quasi-Ramsey of case n, if it has no complete graph Kn in itself or its complementary graph, and if added another vertex, no matter how it is lined to the graph, the derived graph will have Kn in itself or its complementary. When the number of vertices is R(n,n)-1, called it a Ramsey graph. There is a simple example to show the existence of quasi-Ramsey graph. First R(n,n)>n*(n-1). R(n,n)>(n-1)(n-1). Second, choose n n-1 (n-1)-complete graphs Kn-1, without any lines between any two vertices from two distinct Kn-1. This graph with n*(n-1) (n-1)(n-1) vertices is a quasi-Ramsey graph. Furthermore, there are a series of questions about it. For example, if there could be non-isomorphic quasi-Ramsey graphs with same number of vertices, if they are all completely symmetrical (vertex transitive)and how many quasi-Ramsey graphs there are. If all the quasi-Ramsey graphs can be cleared out, we will get a deeper understanding of the structure of Ramsey graphs. Then we are more likely to obtain better estimates of Ramsey numbers. |
||||
|
1 |
|
||

