رنگ آمیزی نقره ای گراف پترسن تعمیم یافته

الموضوعات :

نازلی بشارتی ¹ (گروه ریاضی دانشکده علوم پایه دانشگاه پیام نور تهران ایران)

تاريخ الإرسال : 13 الثلاثاء , ذو القعدة, 1440 تاريخ التأكيد : 24 الإثنين , محرم, 1441 تاريخ الإصدار : 07 الجمعة , رجب, 1442

الکلمات المفتاحية: Independent Set, Chromatic number, Generalized Petersen Graphs, Defining set, Silver coloring,

ملخص المقالة :

فرض‌کنید ".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) نقره‌ای هستند.

المصادر:

[1] M. Mahdian and E. S. Mahmoodian. The roots of an IMO97 problem. Bull. Inst. Combin. Appl., 28:48–54, 2000.

 

[2] Mark E. Watkins. A theorem on Tait colorings with an application to the generalized Petersen graphs. J. Combinatorial Theory, 6:152–164, 1969.

 

[3] Babak Behsaz, Pooya Hatami, and E. S. Mahmoodian. On minimum vertex covers of generalized Petersen graphs. Australas. J. Combin., 40:253–264, 2008.

 

[4] Mehdi Behzad, Pooya Hatami, and E. S. Mahmoodian. Minimum vertex covers in the generalized Petersen graphs ( ,2). Bull. Inst. Combin. Appl., 56:98–102, 2009.

 

[5] J. B.Ebrahimi, Nafiseh Jahanbakht, and E. S. Mahmoodian. Vertex domination of generalized Petersen graphs. Discrete Math., 309(13):4355–4361, 2009.

 

[6] Nazli Besharati, J. B. Ebrahimi, and A. Azadi. Independence number of generalized petersen graphs. Ars Combinatoria, 124 (17): 239–255, 2016.

 

[7] Alice Steimle and William Staton. The isomorphism classes of the generalized Petersen graphs. Discrete Math., 309(1):231–237, 2009.

 

[8] Douglas B. West. Introduction to Graph Theory. Prentice-Hall, Inc, United States of American, 2001.

 

[9] Mohammad Ghebleh, Luis A. Goddyn, E. S. Mahmoodian, and Maryam Verdian-Rizi. Silver cubes. Graphs Combin., 24(5):429–442, 2008.

 

[10] A. Ahadi, Nazli Besharati, E. S. Mahmoodian, and M. Mortezaeefar. Silver block intersection graphs of steiner 2-designs. Graphs Combin., 29(4):735–746, 2013.

 

[11] Diane Donovan, E. S. Mahmoodian, Colin Ramsay, and Anne Penfold Street. Defining sets in combinatorics: a survey. In Surveys in combinatorics, 2003 (Bangor), volume 307 of London Math. Soc. Lecture Note Ser., pages 115–174. Press, Cambridge, 2003.