Relaxed graceful labellings of trees (Q5954317)

Summary: A graph \(G\) on \(m\) edges is considered graceful if there is a labelling \(f\) of the vertices of \(G\) with distinct integers in the set \(\{0,1,\dots,m\}\) such that the induced edge labelling \(g\) defined by \(g(uv)=|f(u)-f(v)|\) is a bijection to \(\{1,\dots,m\}\). We here consider some relaxations of these conditions as applied to tree labellings: 1. Edge-relaxed graceful labellings, in which repeated edge labels are allowed, 2. Range-relaxed graceful labellings, in which the upper bound \(m'\) is allowed to go higher than the number of edges, and 3. Vertex-relaxed graceful labellings, in which repeated vertex labels are allowed. The first of these had been looked at by \textit{A. Rosa} and \textit{J. Širáň} [J. Graph. Theory 19, No. 2, 201-215 (1995; Zbl 0818.05054)]. Here some linear bounds in the relevant metrics are given for range-relaxed and vertex-relaxed graceful labellings.