رنگ آمیزی نقره ای گراف پترسن تعمیم یافته
محورهای موضوعی : آمار
1 - گروه ریاضی، دانشکده علوم پایه، دانشگاه پیام نور، تهران، ایران
کلید واژه: 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) نقره‌ای هستند.
In a graph G=(V,E), an independent set I(G) is a subset of the vertices of G such that no two vertices in I(G) are adjacent. Any maximum independent set of a graph is called a diagonal of the graph. Let c be a proper (r+1)-coloring of an r-regular graph G. A vertex v in G is said to be rainbow with respect to c if every color appears in the closed neighborhood N[v]=N(v)∪{v}. Given a diagonal I of G, the coloring c is said to be silver with respect to I if every v∈I is rainbow with respect to c. G is called silver if it admits a silver coloring with respect to some diagonal. In [1], the authors introduced silver coloring and the following question is raised “Find classes of r-regular graphs G, that G is a silver graph". This paper is aimed toward study this question for the generalized Petersen graphs. In this paper we show that, if n≡0 (mod4) and k is odd, then P(n,k) is a totally silver graph. Also, for every natural number n, the existence of silver coloring for generalized Petersen graphs P(n,1), P(n,2) except for n=5, this is well-known petersen graph, P(n,3) except for n=10,14 and 26. Also, for any k>2,P(2k+1,k), and for any k>3,P(3k+1,k), and for any k>3, k ≠5,9 P(3k-1,k) are silver graphs.
[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.