Silver coloring of generalized Petersen graphs
Subject Areas : Statistics
Nazli Besharati
1
(
Department of Mathematical Sciences, Payame Noor University, P.O. Box 19395-3697, Tehran, Islamic Republic of Iran
)
Keywords: رنگآمیزی نقرهای, مجموعه مستقل, گراف پترسن تعمیمیافته, مجموعهی تعیینکننده, عدد رنگی,
Abstract :
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.