دوستعلی مژده

در این رساله، مطالعه روی احاطه گر دو برابر ایتالیایی )رومی-} ({۳انجام می شود. کمترین وزن تابع احاطه گر دو برابر ایتالیایی مستقل خارجی را عدد احاطه گر دو برابر ایتالیایی مستقل خارجی گوییم و با نماد γoidIنشان می دهیم. هم چنین کمترین وزن تابع احاطه گر دو برابر ایتالیایی همبند را عدد احاطه گر دو برابر ایتالیایی همبند گوییم و با نماد γcdIنمایش می دهیم. ثابت می کنیم که احاطه گر دو برابر ایتالیایی مستقل خارجی و احاطه گر دو برابر ایتالیایی همبند از نوع پیچیدگی زمانی -NPکامل هستند. هم چنین خانواده هایی از گراف ها که عدد احاطه گری دو برابر ایتالیایی مستقل خارجی و همبند آنان در دسته های اعداد کوچک قرار دارند را دسته بندی می کنیم. از طرف دیگر وارد حوزه ضرب گراف ها می شویم؛ مدلهای مختلفی از ضرب گراف ها را برای γoidI بیان می کنیم. ارتباط بین ضرب دکارتی و لکسیکوگرافیک گراف ها و مجموعه مستقل ماکزیمم را برحسب γoidI تشریح می کنیم. بعلاوه،کران های بالا و پایین را برای پارامترهای γoidIو γcdIاثبات می نماییم. از طرف دیگر کران های بالا و پایین مجموعه احاطه گر دو برابر ایتالیایی مستقل خارجی و احاطه گر دو برابر ایتالیایی همبند را روی درختها تشریح می کنیم. رویکرد دیگر مقاله، ارتباط بین پارامترهای γcdIبا γc ،γو γdIاست