-
حرية الوصول المقاله
1 - بررسی بیشینه تعداد رده های احاطه گر در رنگ آمیزی یک گراف
مرتضی فغانیدر این مقاله، عدد رنگی χ-احاطه گر، یعنی d_χ (G) در یک گراف G مورد بررسی قرار می گیرد. این عدد برابر است با ماکزیمم تعداد رده های رنگی که احاطه گر (یا تسلطی) بوده و G توسط χ(G) رنگ، رنگ آمیزی می شود. همچنین، نشان خواهیم داد که d_χ (G∨H)=d_χ (G)+d_& أکثردر این مقاله، عدد رنگی χ-احاطه گر، یعنی d_χ (G) در یک گراف G مورد بررسی قرار می گیرد. این عدد برابر است با ماکزیمم تعداد رده های رنگی که احاطه گر (یا تسلطی) بوده و G توسط χ(G) رنگ، رنگ آمیزی می شود. همچنین، نشان خواهیم داد که d_χ (G∨H)=d_χ (G)+d_χ (H) است بطوریکه G∨H به معنای الحاق G و H است. نتیجه فوق به ما کمک می کند که رده های گراف هایی که d_χ (G)>1 و d_χ (G)=χ(G) است را مشخص نماییم. همچنین در این مقاله، برخی نتایج در ارتباط با عدد رنگی χ-احاطه گر یک گراف ارائه می شود که مرتبط با سوالات مطرح شده در برخی مقالات اخیر حول مشخص سازی گراف های همبند G براساس مقدار d_χ (G) می باشد. در بخش پایانی مقاله، براساس قضایای حاصل این پرسش را مطرح می کنیم که آیا گراف های بدون مثلث G با شرط d_χ (G )=χ(G)=k موجود است؟آیا G دارای یک زیرگراف k-رنگ پذیر یکتا است یا خیر؟ بعلاوه، آیا یافتن چنین گراف هایی از کمر به اندازه کافی بزرگ میسر می باشد؟ تفاصيل المقالة -
حرية الوصول المقاله
2 - عدد احاطه گری وقوعی گراف ها
پریسا عزیزی کشاورز ابوالفضل تهرانیاندر این مقاله مفهوم عدد احاطه گری وقوعی گراف ها معرفی شده و مجموعه احاطه گر وقوعی و عدد احاطه گری وقوعی برخی از گراف های خاص مانند گراف مسیر، گراف دور، گراف چرخ، گراف کامل و گراف ستاره مورد مطالعه قرار گرفته است. ابتدا عدد احاطه گری وقوعی تعدادی از گراف های خاص مانند گرا أکثردر این مقاله مفهوم عدد احاطه گری وقوعی گراف ها معرفی شده و مجموعه احاطه گر وقوعی و عدد احاطه گری وقوعی برخی از گراف های خاص مانند گراف مسیر، گراف دور، گراف چرخ، گراف کامل و گراف ستاره مورد مطالعه قرار گرفته است. ابتدا عدد احاطه گری وقوعی تعدادی از گراف های خاص مانند گراف مسیر، گراف دور، گراف ستاره، گراف چرخ و همچنین گراف کامل محاسبه شده است. سپس عدد رنگی احاطه گر وقوعی برخی از گراف های ذکر شده محاسبه شده و نتایجی در این زمینه به دست آمده است. عدد رنگی احاطه گر وقوعی هر گراف در واقع عدد رنگی احاطه گر برای گراف وقوع است. نشان داده شده که مقدار این عدد برای گراف مسیر از مرتبه n برابراست با ⌈(2(n-1))⁄5⌉+3. همچنین برای گراف دور از مرتبه n مقدار آن برابراست با ⌈2n⁄5⌉+3 . ثابت شده که عدد رنگی احاطه گر وقوعی برای گراف ستاره S_n برابر n+1 بوده و همچنین برای گراف کامل از مرتبه n نشان داده شده که این مقدار برابر n است. تفاصيل المقالة -
حرية الوصول المقاله
3 - رنگ آمیزی نقره ای گراف پترسن تعمیم یافته
نازلی بشارتیفرضکنید ".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) نقرهای هستند. تفاصيل المقالة -
حرية الوصول المقاله
4 - The Chromatic Number of the Square of the Cartesian Product of Cycles and Paths
Sajad Sohrabi Hesan Freydoon Rahbarnia Mostafa TavakoliGiven any graph G, its square graph G^2 has the same vertex set V (G), with two vertices adjacent in G^2 whenever they are at distance 1 or 2 in G. A set S ⊆ V (G) is a 2-distance independent set of a graph G if the distance between every two vertices of S is great أکثرGiven any graph G, its square graph G^2 has the same vertex set V (G), with two vertices adjacent in G^2 whenever they are at distance 1 or 2 in G. A set S ⊆ V (G) is a 2-distance independent set of a graph G if the distance between every two vertices of S is greater than 2. The 2-distance independence number α_2(G) of G is the maximum cardinality over all 2-distance independent sets in G. In this paper, we establish the 2-distance independence number and 2-distance chromatic number for C_3□C_6□C_m, C_n□P_3□P_3 and C_4□C_7□C_n where m ≡ 0 (mod 3) and n,m ⩾ 3. تفاصيل المقالة