Modular gracious labellings of trees (Q5937589)

Let \(T=(V,E)\) be a tree with \(q\) edges. A labeling is a bijection \(g: V\rightarrow \{0,1,\dots,q\}\). Let \(D\) and \(U\) be a bipartition of \(V\) (\(D\) is down and \(U\) is up). Then for every edge \(du\), \(d\in D\), \(u\in U\) the vertex labeling \(g\) induces the label \(g(u)-g(d)\). The labeling \(g\) is gracious if the induced edge labeling is a bijection: \(E\rightarrow\{1,2,\dots,q\}\). The authors conjecture that every tree has a gracious labeling. This conjecture seems to be difficult to prove and the authors propose a related `modulo \(k\)' concept of tree labeling, a gracious \(k\)-labeling. Let \(k>1\) be an integer and let \(Z_k\) be the additive group of integer congruence classes modulo \(k\). For \(x\in Z_k\) define \(\phi_{k,q}(x)\) to be the number of integers in \(\{0,1,\dots,q\}\) belonging to congruence class \(x\). Then \(k\)-labeling of \(T\) is a function \(f: V\rightarrow Z_k\) such that for each \(x\in Z_k\) there are \(\phi_{k,q}(x)\) vertices with the label \(x\). The function \(f\) is a gracious \(k\)-labeling if the induced edge labels are `correctly' distributed over the congruence classes, i.e. there are \(\phi_{k,q}(0) -1\) edges labeled \(0\) and for every \(x\geq 1\), \(x\in Z_k\), \(\phi_{k,q}(x)\) edges labeled \(x\). It is shown that every non-null tree has a gracious \(k\)-labeling for each \(k=2,3,4,5\).