Skip to main content
SUPERVISOR
Gholamreza Omidi,Behnaz Omoomi
غلامرضا امیدی اردلی (استاد راهنما) بهناز عمومی (استاد مشاور)
 
STUDENT
Mahbubeh Lotfi khorzughi
محبوبه لطفی خرزوقی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1389

TITLE

Cycle Complete Graph Ramsey Numbers
For two given graphs G 1 and G 2, the Ramsey number R ( G 1 , G 2 ) is the smallest integer n such that for any graph G of order n, either G contaions G 1 or the complement of G contaions G 2 . In this thesis, we adopt the standard notations C m and K n for the cycle and complete graph on m and n verticese, respectively. an independent et of vertices of a graph G is asubset of V(G) in which no two vertices are adjacent. The independence number ? ( G ) of a graph G is the cardinality of its largest independent et. Give a graph H without isolated vertices, the Ramsey number R ( H, K n ) is the smallest integer N such that of order N either contains H as a subgraph or satiss?es ? ( G ) ? n . Let C m be a cycle of length m and K n be a complete graph of order n . The cycle-complete graph Ramsey number R ( C m , K n ) is the smallest integer N such that for every graph G of order N , G contain C m or ? ( G ) ? n . The graph ( n ? 1) K m ? 1 shows that R ( C m , K n ) ? ( m ? 1)( n ? 1) + 1. Known asymptotic upper bounds on cycle- complete Ramsey numbers for ?x cycle are shown in (1) through (5) below, 1) R ( C 3 ;K n ) _ c 1 n 2 log n ; 2) R ( C 4 ;K n ) _ c 2( n log n )2 ; 3) R ( C 5 ;K n ) _ c 5 n 3 p 2 log n ; 4) R ( C 2 k ;K n ) _ c 2 k ( n log n ) k k ?? 1 ; 5) R ( C 2 k +1 ;K n ) _ c 2 k +1 n 1+1 k ln 1 k ( n ) . Spencer in 1977 using probabilistic method obtained a lower bound c m ( n log n ) m ?? 1 m ?? 2 _ R ( C m ;K n ). Erd?s et al. asked what is minimum value of R ( C m , K n ) for ?xed n, and they suggested that ?rst decreases monotonicaly, then attains a unique minimum, then increases monotonicaly whit m. In one of the earliest contributions to graphical Ramsey theory, Bondy and Erd?s in 1973 proved the following result: for all m ? n 2 ? 2, R ( C m , K n ) = ( m ? 1)( n ? 1) + 1. The restriction was improved by Schiermeyer in 2003 when he showed that the equality holds for n ? 5 whit m ? n 2 ? 2 n , and in 2005 by Nikiforov, when he proved the equality for m ? 4 n + 2. In 1978, Erd?s, Faudree, Schelp and Rousseau gave the following conjecture. Conjecture ( Erd?s et al.) : R ( C m , K n ) = ( m ? 1)( n ? 1) + 1, for all m ? n ? 3 (except R ( C 3 , K 3) = 6). The conjecture was confrimed by Faudree and Schelp in 1973 and Rousta in 1974 for n = 3 in early work on Ramsey theory. heng et al. in 1999, and Bollob?s et al. in 2000 proved the conjecture for n = 4 and n = 5, respectively. The conjecture was proved by Schiermeyer in 2003 for n = 6. Chena et al. in 2007 proved the conjectur for n = 7. the conjecture is still open. Researchers are intrested in determining all the value of the Ramsey number R ( C m , K 8). In this thesis, we stady the best known upper bound on R ( C m , K n ) for odd m, and R ( C m , K n ) for 3 ? n ? 7.
یکی از موضوعات مهم در نظریه گراف, مطالعه‌ی اعداد رمزی گراف‌هاست. برای دو گراف G ?و G ? عدد رمزی ، R ( G ? , G ?) کوچکترین n ای است که برای هر گراف G از مرتبه‌ی ، n گراف G شامل G ?و یا مکمل G شامل G ? باشد. C m را دوری به طول m و K n را گراف کامل از مرتبه‌ی n در نظر می‌گیریم, مسأله‌ی اصلی این پایان نامه مطالعه‌ی عدد رمزی R ( C m , K n ) است. گراف G = ( n ? ?) K m ? ?فاقد دور C m و K n است بنابراین R ( C m , K n ) ? ( m ? ?)( n ? ?) + ?. بخش مشکل تر مسأله مورد نظر یافتن کران بالا برای R ( C m , K n ) است. در مورد محاسبه‌ی دقیق مقدار R ( C m , K n ) اردوش و همکارانش در سال 1978 حدس R ( C m , K n ) = ( m ? ?)( n ? ?) + ? را برای m ? n ? ? و ( m, n ) = (? , ?) مطرح کردند. تاکنون این حدس برای ? ? n ? ? ثابت شده, ولی برای دیگر مقادیر m و هنوز باز است. هدف این پایان نامه مطالعه‌ی درستی حدس اردوش و همکارانش برای ? ? n ? ? است. به‌علاوه نتیجه‌ی به دست آمده در مورد R ( C m , K n ) برای mهای فرد مورد مطالعه قرار گرفته است. هم‌چنین به نتایج به‌دست آمده در مورد R ( C m , K n ) برای m های بزرگ اشاره می‌کنیم.

ارتقاء امنیت وب با وف بومی