\(\alpha\)-labeling number of trees (Q856879)

This paper is concerned with \(\alpha\)-labellings of graphs, introduced by Rosa in the 1960's in connection with the decomposition of complete graphs into trees. Due to the difficulty of Rosa's problem, a number of variations have been introduced. In relation to one of these, the notion of the \(\alpha\)-labeling number of a graph was introduced by Snevily in 1997. \(H\) is a host graph of \(G\) if \(H\) has an \(\alpha\)-labeling and can be decomposed into copies of \(G\). The \(\alpha\)-labeling number of \(G\) is defined by \(G_{\alpha}=\) min \(\{t \mid\) there is a host graph \(H\) of \(G\) with \(| E(H)| =t| E(G)|\}\). Snevily conjectured that for a tree \(T\) with \(n\) edges, \(T_{\alpha} \leq n\) and proved that \(T_{\alpha} \leq 2^{n-1}\). The first author of the paper at hand improved this to \(T_{\alpha} \leq e^{O(\sqrt{n\log n})}\). In the current paper this is improved to the quadratic bound \(T_{\alpha} \leq \lceil r/2 \rceil n\), where \(r\) is the radius of \(T\). The proof is interesting and constructive in the sense that it involves definining an actual family of graphs with \(\lceil r/2 \rceil n^{2}\) edges which serve as host graphs of arbitrary trees with \(n\) edges.