ГлавнаяАрхивОб индексе палитры треугольника Серпинского и графа Серпинского

Об индексе палитры треугольника Серпинского и графа Серпинского | Прикладная дискретная математика. 2021. № 54. DOI: 10.17223/20710410/54/5

Палитра вершины v графа G в правильной раскраске рёбер - это набор цветов, присвоенных рёбрам, инцидентным v. Индекс палитры G - это минимальное количество палитр из всех правильных рёберных раскрасок G. Рассматриваются индексы палитры графов Серпинского Snp и треугольников Серпинского Sn3. Доказано, что индекс палитры треугольника Серпинского Sn3равен 3, если n чётное, и 4 иначе; индекс палитры графа Snp равен 2 для чётного p и равен 3 для p = 3 или n = 2 и p = 4l + 3.
  • Title Об индексе палитры треугольника Серпинского и графа Серпинского
  • Headline Об индексе палитры треугольника Серпинского и графа Серпинского
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 54
  • Date:
  • DOI 10.17223/20710410/54/5
Ключевые слова
индекс палитры графа, треугольник Серпинского, граф Серпинского
Авторы
Ссылки
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.
Об индексе палитры треугольника Серпинского и графа Серпинского | Прикладная дискретная математика. 2021. № 54. DOI: 10.17223/20710410/54/5
Об индексе палитры треугольника Серпинского и графа Серпинского | Прикладная дискретная математика. 2021. № 54. DOI: 10.17223/20710410/54/5