|
Abstract
|
یک ائتلاف در گراف G متشکل از دو مجموعه جدا از هم V1 و V2 از مجموعه رئوس گراف G است بطوریکه اتحاد آنها یک مجموعه احاطه گر است ولی هیچکدام از آن دو مجموعه احاطه گر برای گراف G نیست. افراز ائتلافی که c- افراز نامیده می شود یک افراز رأسی مانند {V1, V2, …, Vk} است که در آن هرمجموعه Vi یا یک مجموعه احاطه گر تک عضوی است یا یک مجموعه احاطه گر نبوده اما با یک مجموعه دیگر Vj یک ائتلاف تشکیل می دهد. عدد ائتلاف برابر با ماکسیمم تعداد کلاس ها در یک c- افرازگراف G است که با نماد C(G) نمایش داده می شود. برخی از نتایج مهم برای عدد ائتلاف عبارتند از:
1)-اگر G گرافی از مرتبه n باشد آنگاه 1≤ c(G) ≤ n.
2)-اگر G گرافی بدون رأس ایزوله و بدون رأس جهانی باشد آنگاه 4 ≤ d(G) ≤ C(G) ≤ n.
3)-اگر G گرافی بدون رأس جهانی باشد آنگاه C(G) 2+δ(G) ≤.
|