LOCKS AND FORBIDDEN CONFIGURATIONS IN 4-GRACEFUL TREES

Abstract

Let \(f\) be a proper coloring of the vertices of a simple graph \(G\) into colors from the set of colors \(\{1, 2, \dots, k\}\). A coloring \(f\) on the set of edges of a graph \(G\) induces a function \(f'(e) = \vert{}f(u) - f(v)\vert{}\), where \(e = uv\) is an arbitrary edge of the graph \(G\). A coloring \(f\) is called a  \(k\)-graceful coloring  of a graph \(G\) if \(f^{\prime }\) is an edge proper coloring of this graph. We will call a graph a  \(k\)-graceful graph or, simply, graceful graph if it has a \(k\)-graceful coloring. In this paper, we continue the study of 4-graceful trees. We introduce the concept of a lock in a tree \(T\) with maximum vertex degree \(\Delta = 3\). A lock is a configuration \(H\) in \(T\) whose main property is the presence of two special vertices \(u\) and \(v\) such that for any 4-graceful colorings of \(T\), the pair of vertices \(u\) and \(v\) has a unique coloring in the colors from the set \(\{1, 2, 3, 4\}\) up to duality. The main goals of this work are as follows: 1) to construct some simple locks and indicate procedures whose application to known locks generates new locks (see Theorem 1); 2) to use locks and nodal 1-components for finding forbidden configurations for 4-graceful trees (see Propositions 1 and 2, as well as Theorem 2).