كليدواژه :
عدد رنگي , مجموعه‌ي تعيين‌كننده , رنگ‌آميزي نقره‌اي , گراف پترسن تعميم‌يافته , مجموعه مستقل
چكيده فارسي :
فرض‌كنيد ".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.
