Skip to main content
SUPERVISOR
Ramin Gavadi jourtani,Gholamreza Omidi
رامین جوادی جورتانی (استاد مشاور) غلامرضا امیدی اردلی (استاد راهنما)
 
STUDENT
Maryam Moslehi Baharanchi
مریم مصلحی بهارانچی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1395
In this thesis, we study the ramsey goodness of paths and bounded degree trees. Given a pair of graphs G and H, the Ramsey number R(G,H) is defined to be the smallest positive integer n such that every ?-coloring of the edges of the complete graph Kn with colors red and blue contains a red copy of G or a blue copy of H. Frank Ramsey proved these numbers are always finite, therefore R(G,H) is a meaningful definition. Determining or computing the Ramsey number is one of the most important and difficult problems in Combinatorics. In this thesis, it is shown that we can compute R(G,H) with a simple formula for graphs G and H with special properties. Let G is a connected graph and H is a graph with chromatic number #??;X(H) (the smallest number of colors needed to color the vertices of H so that no pair of adjacent vertices have the same color) and the parameter X #??;(H) (the size of the smallest color class between all of #??;X(H)-coloring of H).
برای دو گراف دلخواه G و H، عدد رمزی R(G,H) کوچک ترین عدد طبیعی n تعریف می شود به طوری که گراف کامل Kn در هر ?-رنگ آمیزی دلخواه از یال هایش با دو رنگ قرمز و آبی، یک کپی قرمز از G یا یک کپی آبی از H داشته باشد. اگر G گرافی همبند باشد، واضح است که R(G,H) gt;= (|G|-?)(X(H)-?) #??;\\sigma(H) که X(H) عدد رنگی گراف H و \\sigma(H) اندازه ی کوچک ترین کلاس رنگی در بین تمام رنگ آمیزی های مجاز H با X(H) رنگ است. گراف H را H-مطلوب می نامیم، هرگاه R(G,H) = (|G|-?)(X(H)-?) #??;\\sigma(H) مفهوم مطلوبیت رمزی اولین بار توسط بور و اردوش در سال 1983 معرفی شد و بعد از آن مطالعات گسترده ای روی آن صورت گرفت. در این پایان نامه قصد داریم مطلوبیت رمزی را پیرامون گراف های تنک، نظیر مسیرها و درخت ها بررسی کنیم. هم چنین نشان می دهیم برای گراف دلخواه H، مسیر Pn با مرتبه ی n gt;= ?|H|، H-مطلوب است. اثبات این مسأله را از مقاله ای از سوداکوو و پکرووسکی ارایه می دهیم. در ادامه نشان می دهیم برای گراف دلخواه H، هر درخت از درجه کران دار T که مرتبه ی آن در شرط n gt;=\\omega(|H|log^{?}(|H|)) صدق می کند، H-مطلوب است. اثبات این مسأله نیز در مقاله ای از سوداکوو، پکرووسکی و بالا ارایه می شود.

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