بررسي حدسي از اردوش و فيودري روي اعداد رمزي اندازه‌اي گراف‌هاي كامل-تطابق‌ها

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

رياضي كاربردي

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

چكيده: فرض كنيد گراف هاي H ، F و G دلخواه هستند. عددرمزي اندازه اي براي زوج (H ,F )كوچك ترين عدد طبيعي m است، بطوري كه گراف m يالي مانند G وجود دارد كه در هر دو رنگ آميزي از يال هاي گراف G با دو رنگ آبي وقرمز يا يك كپي آبي رنگ از گراف H وجود داشته باشد يا يك كپي قرمز رنگ از گراف F وجود داشته باشد. عدد رمزي يالي گراف ها نخستين بار توسط اردوش، فيودري، روسي و شلپ مورد مطالعه قرار گرفت. از آن زمان تا كنون عدد رمزي يالي گراف ها با تمركز ويژه اي برروي گراف هاي با ماكزيمم درجه كراندار مورد مطالعه قرار گرفته است. همچنين تعيين عدد رمزي يالي يك گراف نسبتاً پر يال و يك گراف كم يال نيز اهميت ويژه اي برخوردار بوده است. يكي از مهم ترين مساله ها در اين زمينه تعيين مقدار دقيق عدد رمزي اندازه اي گراف كامل و گراف تطابق است. اين مساله در سال 1981 توسط اردوش و فيودري مورد مطالعه قرار گرفت. آنها با طرح يك پرسش تعيين مقدار دقيق عدد رمزي اندازه اي گراف كامل و گراف تطابق را مطرح كردند. اين پرسش در سال 2018 توسط اميدي و جوادي پاسخ داده شد. در اين رساله ما به بررسي مساله عدد رمزي اندازه اي گراف كامل و تطابق پرداخته و نتايج بدست آمده در اين راستارا مورد مطالعه قرار مي دهيم. . كلمات كليدي: اعداد رمزي، اعداد رمزي اندازه اي، تطابق، گراف كامل.

223555

علوم داده

رياضي

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