گراف همسایه مشترک

الموضوعات :

سمانه حسین‌زاده ¹ , علی ایرانمنش ² , اسما حمزه ³ , محمدعلی حسین‌زاده ⁴

1 - دانشکده علوم ریاضی، دانشگاه تربیت مدرس، تهران، ایران.
2 - دانشکده علوم ریاضی، دانشگاه تربیت مدرس، تهران، ایران.
3 - دانشکده علوم ریاضی، دانشگاه تربیت مدرس، تهران، ایران.
4 - دانشکده علوم ریاضی، دانشگاه تربیت مدرس، تهران، ایران.

تاريخ الإرسال : 11 الخميس , ربيع الثاني, 1437 تاريخ التأكيد : 12 الثلاثاء , رجب, 1437 تاريخ الإصدار : 14 السبت , شعبان, 1437

الکلمات المفتاحية: Common neighborhood graph, Hamiltonian cycle, Clique number, Graph operation,

ملخص المقالة :

فرض کنید ‎G یک گراف ساده با مجموعه رأس‌های ‎است. گراف همسایه مشترک که با  ‎ نشان داده می‌شود، گرافی است با مجموعه رأس‌های‎  و دو رأس در آن مجاورند اگر دست کم یک همسایه مشترک داشته باشند. در این مقاله گراف همسایه مشترک تعدادی گراف‌های ترکیبی را محاسبه می‌کنیم. همچنین به بررسی رابطه همیلتونی بودن گراف و  پرداخته و کران پایینی برای عدد خوشه گراف ‎  برحسب عدد خوشه گراف  به دست می‌آوریم. در ادامه نشان می‌دهیم عدد رنگی کلی گراف ‎  به وسیله عدد رنگی‎  محدود می‌شود.