فرضکنید ".G=(V,E)" زیرمجموعه Iاز رأسهای گراف را یک مجموعه مستقل مینامند، هرگاه هیچ دو رأسی از I در G مجاور نباشند. هر مجموعه مستقل ماکزیمم از گراف را یک قطر گراف مینامند. فرضکنید" c" یک"(r+1)" -رنگآمیزی معتبر برای گراف "r" -منتظم "G" باشد. رأس v نسبت به رنگآمیزی
چکیده کامل
فرضکنید ".G=(V,E)" زیرمجموعه Iاز رأسهای گراف را یک مجموعه مستقل مینامند، هرگاه هیچ دو رأسی از I در G مجاور نباشند. هر مجموعه مستقل ماکزیمم از گراف را یک قطر گراف مینامند. فرضکنید" c" یک"(r+1)" -رنگآمیزی معتبر برای گراف "r" -منتظم "G" باشد. رأس v نسبت به رنگآمیزی c رنگینکمان است، هرگاه همهی رنگها در همسایگی بسته "N[v]=N(v)∪{v}" ، ظاهر شوند. فرضکنید I یک قطر، برای گراف r-منتظم "G" باشد. یک "(r+1)" -رنگآمیزی معتبر "c" را رنگآمیزی نقرهای نسبت بهI مینامند، هرگاه هر رأس "v∈I" رنگینکمان باشد. گراف" G" را نقرهای مینامند، اگر دارای یک رنگآمیزی نقرهای نسبت به I باشد. در مقاله [1]، این مسأله مطرح گردیده است: "خانواده گرافهای r-منتظم "G" را تعیین کنید که نقرهای باشند." برای پاسخ دادن به این سؤال در این مقاله، گرافهای پترسن تعمیمیافته را در نظر گرفتهایم. در این مقاله، نشان میدهیم گراف پترسن تعمیمیافته P(n,k) ، به ازای n≡0 (mod4) و k یک عدد فرد، یک گراف کاملاً نقره ای است. همچنین، نشان میدهیم برای هر عدد طبیعیn، یک رنگ آمیزی نقرهای برای گرافهای پترسن تعمیم یافتهP(n,1)، P(n,2) (n>5) و P(n,3) n≠10,14,26، نسبت به یک مجموعه مستقل ماکزیمم آن وجود دارد. همچنین، به ازای هر k>2، گراف P(2k+1,k)، به ازای هر k>3 ، گراف P(3k+1,k) و به ازای هرk ≠5,9،k>3 ، گراف P(3k-1,k) نقرهای هستند.
پرونده مقاله