$4$-graceful trees

V. A. Baranskii ; I. A. Nasyrov ; T. A. Senchonok

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 30 (2024) no. 4, pp. 64-76

Résumé

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.

Détail

Keywords: graph, tree, graceful coloring of a graph, graceful trees.

Bibliographie

[1] Asanov M.O., Baranskii V.A., Rasin V.V., Diskretnaya matematika: grafy, matroidy, algoritmy, 2-e izd., ispr. i dop., Lan, SPb., 2010, 368 pp.

[2] Chartrand G., Zhang P., Chromatic graph theory, Discrete mathematics and its applications, Chapman Hall/CRC Press, Boca Raton, 2009, 504 pp. | Zbl

[3] Gallian J.A., “A dynamic survey of graph labeling”, Electron. J. Comb., 1998, DS6, 43 pp. | DOI | MR | Zbl

[4] English E., Zhang P., “On graceful colorings of trees”, Mathematica Bohemic, 142:1 (2016), 57–73 | DOI | MR

[5] Byers A.D., Graceful colorings and connection in graphs, Diss. Doct. at Western Michigan University, Dissertations 3308, 2018, 102 pp. 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., 9:2 (2023), 193–208 | DOI | MR | Zbl