اعداد رمزي براي دو مجموعه از دورها

اصفهان : دانشگاه صنعتي اصفهان

رياضي

كارشناسي ارشد

چكيده براي دو مجموعه داده شده G_1 و G_2 از گراف‌ها، عدد رمزي تعميم يافته R(G_1,G_2) كوچكترين عدد صحيح N است به طوري كه براي هر گراف G روي N راس، يا G داراي عضوي از G_1 است يا مكمل G داراي يك عضوي از G_2 است. واضح است كه R(G_1,G_2)=R(G_2,G_1). هنگامي كه |G_1 |=|G_2 |=1 باشد، عدد رمزي تعميم يافته R(G_1,G_2) به عدد رمزي معمولي R(G_1,G_2) براي دو گراف داده شده G_1 و G_2 كاهش مي‌يابد. به راحتي مي‌توان ديد كه براي هر G_1∈G_1 و G_2∈G_2، رابطه R(G_1,G_2)≤R(G_1,G_2) برقرار است. در اين پايان‌نامه، روي R(C_1,C_2)، تمركز مي‌كنيم كه هر C_i مجموعه‌اي از دورها است. براي دو خانواده داده شده C_1 و C_2 از دورها، عدد رمزي تعميم يافته جفت (C_1,C_2) نشان داده شده با R(C_1,C_2)، برابر با كوچكترين عدد صحيح N تعريف مي‌شود، به طوري كه براي هر گراف G بر روي N راس، يا G شامل يك دور از C_1 يا مكمل G شامل يك دور از C_2 باشد. در سراسر اين پايان‌نامه، (C_1,C_2) يك جفت خانواده غير تهي از دورها را نشان مي‌دهد، كه مي‌خواهيم اعداد رمزي تعميم يافته R(C_1,C_2) را محاسبه كنيم. تمام گراف‌هاي اين تحقيق متناهي، ساده و بدون جهت هستند. علاوه بر اين، (G_1,G_2) يك جفت گراف غير تهي و (G_1,G_2) يك جفت خانواده غير تهي از گراف‌هاي غير تهي را نشان مي‌دهد. بنابراين، نتايجي را ارائه مي‌كنيم كه شامل تمام مقادير دقيق قبلي شناخته شده اعداد رمزي تعميم‌يافته براي دو خانواده دور است. وقتي |C_1 |=|C_2 |=1، اعداد رمزي معمولي R(C_1,C_2) به طور مستقل توسط فادريFaudree و شلپ Schelp [?] و رستاRosta [?] تعيين شدند. يك اثبات جديد، ساده تر، اما هنوز كاملاً فني و مفصل، توسط كاروليKárolyi و رستا [?] ارائه شده است. رده‌بندي موضوعي: 55C05، 10D05 واژگان كليدي: اعداد رمزي، خانواده‌اي از دورها، همه دوري ضعيف

232775

گراف و تركيبيات

رياضي

دانشگاه صنعتي اصفهان