تابع و عدد غالب رومی و ایتالیایی گراف

فرض کنید (e ,v = (g یک گراف ساده است. زیرمجموعه v ⊆ s یک مجموعه غالب (احاطه گر) گرافg است، هرگاه هر راس خارج از مجموعه s با حداقل یک راس از s مجاور باشد. اندازه کوچک ترین مجموعهغالب g را عدد غالب می گویند و آن را با (g(γ نشان می دهند. یک تابع غالب رومی روی گراف g تابعی مانند{2 1, 0,} → (g (v : f است به طوری که هر راس v با 0 = (v(f مجاور حداقل یک راس با برچسب 2باشد. وزن تابع غالب رومی f برابر مجموع همه برچسب های داده شده به رئوس تحت f است. عدد غالب رومیg برابر با مینیمم وزن تابع غالب رومی گراف g است و با نماد (g(γr نشان داده می شود. یکی از تعمیم هایتابع و عدد غالب رومی، تابع و عدد غالب ایتالیایی است. یک تابع غالب ایتالیایی روی گراف g تابعی مانند{2 1, 0,} → (g (v : f است به طوری که هر راس v با 0 = (v(f مجاور حداقل دو راس با برچسب 1 و یاحداقل مجاور یک راس با برچسب 2 باشد. وزن تابع غالب ایتالیایی f برابر مجموع همه برچسب های داده شده بهرئوس تحت f است. عدد غالب ایتالیایی g برابر با مینیمم وزن تابع غالب ایتالیایی گراف g است و با نماد (g (γiنشان داده می شود. در این مقاله، عدد غالب رومی ایتالیایی و تعداد مجموعه های غالب رومی و ایتالیایی با وزن i رابرای برخی گراف های خاص مطالعه خواهیم کرد