\(\rho\)-valuations for some stunted trees (Q2433736)

A \(\rho\)-valuation of a graph \(G\) with \(n\) edges is an injection of the vertex set into the set \(\{0,\dots,2n\}\) so that, if the edge labels induced by the absolute value of the difference of the vertex labels are \(a_1,a_2,\dots,a_n\), then \(a_i=i\) or \(a_i=2n+1-i\). This is one of the valuations introduced by \textit{A. Rosa} [Theory Graphs, Int. Symp. Rome 1966, 349--355 (1967; Zbl 0193.53204)]. There is a conjecture due to \textit{A. Kotzig} [Util. Math. 4, 261--290 (1973; Zbl 0277.05102)] that all trees have \(\rho\)-valuations. The article under review gives a partial answer to this conjecture. A tree with \(n\) edges is stunted if its edges can be linearly ordered \(e_1,e_2,\dots,e_n\) so that \(e_1\) and \(e_2\) share a vertex, and for all \(j=3,\dots,n\), \(e_j\) shares a vertex with at least one edge \(e_k\) satisfying \(2k\leq j-1\). Using the combinatorial Nullstellensatz by \textit{N. Alon} [Comb. Probab. Comput. 8, 7--29 (1999; Zbl 0920.05026)], the author proves that if \(p=2n+1\) is prime, then every stunted tree with \(n\) edges has a \(\rho\)-valuation. As a corollary, every stunted tree with \(n\) edges cyclically decomposes the complete graph \(K_{2n+1}\) by a result of A. Rosa. A tree \(T\) with \(n\) edges cyclically decomposes \(K_{2n+1}\) if there exists an injection \(\psi:V(T) \to \mathbb{Z}_{2n+1}\) such that for all distinct \(i,j\in \mathbb{Z}_{2n+1}\), there exists a unique \(k\in \mathbb{Z}_{2n+1}\) with the property that there is a pair of adjacent vertices \(u\), \(v\) of \(T\) satisfying \(\{i,j\}\equiv \{\psi(u)+k\), \(\psi(v)+k\}\).