УДК 519.174.7
MSC: 05C15
DOI: 10.21538/0134-4889-2024-30-4-64-76
Пусть $f$ — раскраска вершин связного графа $G$ в краски из множества красок $\{1, 2, \dots, k\}$. Раскраска $f$ на множестве ребер графа $G$ индуцирует функцию $f'(e) = |f(u) - f(v)|$, где $e = uv$ — произвольное ребро графа $G$. Число $f'(e)$ будем называть цветом ребра $e$, индуцированным раскраской $f$. Раскраска $f$ называется изящной $k$-раскраской графа $G$, если $f'$ является реберной раскраской этого графа. Граф будем называть $k$-изящным или, просто, изящным, если он обладает изящной $k$-раскраской. Основная цель нашей работы — дать два достаточных условия, каждое из которых гарантирует 4-изящность деревьев (см. теоремы 1 и 2). Кроме этого мы исследуем свойства 4-изящных графов для доказательства теорем 1 и 2. Найденные свойства мы также используем в следующих работах для изучения 4-изящных графов и 4-изящных деревьев в общем случае. Отметим, что 4-изящные деревья устроены достаточно сложно, а 3-изящные связные графы устроены очень просто. Они исчерпываются простыми цепями длины не более 3. Нетрудно установить, что любой 4-изящный граф не содержит вершин степени, большей 3. Поэтому мы рассматриваем деревья $T$, степени вершин которых не превосходят числа 3. Вершины степени 3 в дереве $T$ мы будем называть узлами. Будем говорить, что для двух узлов $u$ и $v$ дерева $T$ узловое расстояние между ними равно числу $t$, если существует простая цепь от $u$ до $v$, число внутренних вершин в которой равно $t\geq 1$ и все эти внутренние вершины имеют степень 2 в дереве $T$. Конечно, узловое расстояние определено не для каждой пары узлов. Среди прочих свойств 4-изящных графов установлено, что такие графы не содержат простых цепей, состоящих из трех узлов. Указанные нами достаточные условия 4-изящности деревьев состоят в запрете появления в них пар узлов, узловое расстояние между которыми равно 1 или 2.
Ключевые слова: граф, дерево, изящная раскраска графа, изящные деревья
СПИСОК ЛИТЕРАТУРЫ
1. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. 2-е изд., испр. и доп. СПб.: Лань, 2010. 368 c.
2. Chartrand G., Zhang P. Chromatic graph theory. Discrete mathematics and its applications. Boca Raton: Chapman & Hall/CRC Press, 2009. 504 p.
3. Gallian J.A. A dynamic survey of graph labeling // Electron. J. Comb. 1998. DS6. 43 p. doi: 10.37236/27
4. English E., Zhang P. On graceful colorings of trees // Mathematica Bohemic. 2016. Vol. 142, no. 1. P. 57–73. doi: 10.21136/MB.2017.0035-15
5. Byers A.D. Graceful colorings and connection in graphs: Diss. Doct. at Western Michigan University, 2018. Dissertations 3308. 102 p. URL: https://scholarworks.wmich.edu/dissertations/3308 .
6. Suparta I.N., Venkathacalam M., Gunad I Gede A.I„ Pratama Putu A.C. Graceful chromatic number of some Cartesian product graphs // Ural Math. J. 2023. Vol. 9, no. 2. P. 193–208. doi: 10.15826/umj.2023.2.016
Поступила 29.09.2024
После доработки 8.10.2024
Принята к публикации 14.10.2024
Баранский Виталий Анатольевич
д-р физ.-мат. наук, профессор
профессор
Уральский федеральный университет
г. Екатеринбург
e-mail: vitaly.baransky@urfu.ru
Насыров Илья Александрович
ведущий инженер
Уральский федеральный университет
г. Екатеринбург
e-mail: ilia.nasyrov@urfu.ru
Сеньчонок Татьяна Александровна
канд. физ.-мат. наук
доцент
Уральский федеральный университет
г. Екатеринбург
e-mail: tatiana.senchonok@urfu.ru
Ссылка на статью: В.А. Баранский, И.А. Насыров, Т.А. Сеньчонок. 4-изящные деревья // Тр. Ин-та математики и механики УрО РАН. 2024. Т. 30, № 4. С. 64-76
English
V.A. Baransky, I.A. Nasyrov, T.A. Sen’chonok. 4-graceful trees
Let $f$ be a coloring of the vertices of a connected graph $G$ into colors from a set $\{1, 2, \dots, k\}$. The coloring $f$ induces on the set of edges of $G$ a function $f'(e) = |f(u) - f(v)|$, where $e = uv$ is an arbitrary edge of $G$. The integer $f'(e)$ will be called the color of the edge $e$ induced by the coloring $f$. The coloring $f$ is called a graceful $k$-coloring of $G$ if $f'$ is an edge coloring of this graph. We will call a graph $k$-graceful or, simply, graceful if it has a graceful $k$-coloring. The main goal of our work is to give two sufficient conditions, each of which guarantees the 4-gracefulness of trees (see Theorems 1 and 2). In addition, we study the properties of 4-graceful graphs to prove these theorems. We also plan to use the found properties in the subsequent works on 4-graceful graphs and 4-graceful trees in the general case. Let us note that the 4-graceful trees are quite complex, while the 3-graceful connected graphs have a very simple structure. The latter are limited to simple chains of length at most 3. It is easy to establish that any 4-graceful graph does not contain vertices of degree greater than 3. Therefore, we consider trees $T$ whose vertex degrees do not exceed 3. We will call vertices of degree 3 in a tree $T$ nodes. For two nodes $u$ and $v$ of a tree $T$, we will say that the nodal distance between them is $t$ if there is a simple chain from $u$ to $v$ such that the number of internal vertices of this chain is $t\geq 1$ and all these internal vertices have degree 2 in the tree $T$. Of course, the nodal distance is not always defined for a pair of nodes. Among other properties of 4-graceful graphs, it established that such graphs do not contain simple chains consisting of three nodes. The sufficient conditions for 4-gracefulness formulated in the paper consist in prohibiting the appearance in trees of pairs of nodes whose nodal distances are equal to 1 or 2.
Keywords: graph, tree, graceful coloring of a graph, graceful trees
Received September 29, 2024
Revised October 8, 2024
Accepted October 14, 2024
Vitaly Anatol’evich Baransky, Dr. Phys.-Math. Sci., Prof., Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: vitaly.baransky@urfu.ru
Ilia Aleksandrovich Nasyrov, PhD student, Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: ilia.nasyrov@urfu.ru
Tatiana Aleksandrovna Sen’chonok, Cand. Sci. (Phys.-Math.), Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: tatiana.senchonok@urfu.ru
[References -> on the "English" button bottom right]
Cite this article as: V.A. Baransky, I.A. Nasyrov, and T.A. Sen’chonok. 4-graceful trees. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2024, vol. 30, no. 4, pp. 64–76.
