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
1. Asanov M.O., Baranskiy V.A., Rasin V.V. Diskretnaya matematika: grafy, matroidy, algoritmy [Discrete mathematics: graphs, matroids, algorithms]. 2nd ed. St. Petersburg, Lan’ Publ., 2010, 368 p. ISBN: 978-5-8114-1068-2 .
2. Chartrand G., Zhang P. Chromatic graph theory (Discrete mathematics and its applications). Boca Raton, Chapman & Hall/CRC Press, 2009, 498 p. ISBN: 978-1584888000 .
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. Math. Bohemic, 2017, vol. 142, no. 1, pp. 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. Available at: 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, pp. 193–208. doi: 10.15826/umj.2023.2.016
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.
