The palette of a vertex v of a graph G in a proper edge coloring is the set of colors assigned to the edges which are incident to v. The palette index of G is the minimum number of palettes occurring among all proper edge colorings of G. In this paper, we consider the palette index of Sierpinski graphs Snp and Sierpinski triangle graphs Sn3. In particular, we determine the exact value of the palette index of Sierpinski triangle graphs. We also determine the palette index of Sierpinski graphs Snp where p is even, p = 3, or n = 2 and p = 4l + 3.
Download file
Counter downloads: 37
- Title The palette index of Sierpinski triangle graphs and Sierpinski graphs
- Headline The palette index of Sierpinski triangle graphs and Sierpinski graphs
- Publesher
Tomsk State University
- Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 54
- Date:
- DOI 10.17223/20710410/54/5
Keywords
palette index, Sierpinski triangle graph, Sierpinski graphAuthors
References
West D. Introduction to Graph Theory. Prentice-Hall, 2014.
Hornak M., Kalinowski R., Meszka M., and Wozniak M. Minimum number of palettes in edge colorings. Graphs Combin., 2014, vol. 30, pp. 619-626.
Bonvicini S. and Mazzuoccolo G. Edge-colorings of 4-regular graphs with the minimum number of palettes. Graphs Combin., 2016, vol. 32, pp. 1293-1311.
Holyer I. The NP-completeness of edge-coloring. Siam J. Comput., 1981, vol. 10, pp. 718-720.
Avesani M., Bonisoli A., and Mazzuoccolo G. A family of multigraphs with large palette index. Ars Math. Contemp., 2019, vol. 17, pp. 115-124.
Hornak M. and Hudak J. On the palette index of complete bipartite graphs. Discussiones Mathematicae Graph Theory, 2018, vol. 38, pp. 463-476.
Casselgren C. and Petrosyan P. Some results on the palette index of graphs. Discrete Math. Theor. Comput. Sci., 2019, vol. 21, no. 3, A2.
Bonisoli A., Bonvicini S., and Mazzuoccolo G. On the palette index of a graph: the case of trees. Lecture Notes of Seminario Interdisciplinare di Matematica, 2017, vol. 14, pp. 49-55.
Klavzar S. and Milutinovic U. Graphs S(n, k) and a variant of the Tower of Hanoi problem. Czechoslovak Math. J., 1997, vol. 47, no. 122, pp. 95-104.
Scorer R., Grundy P., and Smith C. Some binary games. Math. Gaz., 1944, vol. 28, pp. 96-103.
Hinz A., Klavzar S., and Zemljic S. A survey and classification of Sierpinski-type graphs. Discrete Math., 2017, vol. 217, no. 3, pp. 565-600.
Klavzar S. Coloring Sierpinski graphs and Sierpinski triangle graphs. Taiwan J. Math., 2008, vol. 12, pp. 513-522.
Jakovac M. and Klavzar S. Vertex-, edge-, and total-colorings of Sierpinski-like graphs. Discrete Math., 2009, vol. 309, no. 6, pp. 1548-1556.
Teguia A. and Godbole A. Sierpinski triangle graphs and some of their properties. Australas. J. Combin., 2006, vol. 35, pp. 181-192.
Hinz A. and Schief A. The average distance on the Sierpinski gasket. Probab. Theory Related Fields, 1990, vol. 87, pp. 129-138.
Kaimanovich V. Random walks on Sierpinski graphs: hyperbolicity and stochastic homogenization. P. Grabner, W. Woess (eds.) Fractals in Graz 2001. Trends in Mathematics. Birkhauser, Basel, 2003, pp. 145-183.
Imran M., Hafi S., Gao W., and Farahani M. R. On topological properties of Sierpinski networks. Chaos Soliton. Fract., 2017, vol. 98, pp. 199-204.

The palette index of Sierpinski triangle graphs and Sierpinski graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2021. № 54. DOI: 10.17223/20710410/54/5
Download full-text version
Counter downloads: 69