Trees Which Admit No \(\alpha\)-labelings

Abstract

In this paper, we study the existence of \(\alpha\)-labelings for trees by means of particular \((0, 1)\)-matrices called \(a\)-labeling matrices. It is shown that each comet \(S_{k, q}\) admits no \(a\)-labelings whenever \(k > 4(q – 1)\) and \(q \geq 2\). We also give the sufficient conditions for the nonexistence of \(a\)-labelings for trees of diameter at most six. This extends a result of Rosa’s. As a consequence, we prove that \(S_{k, 3}\) has an \(a\)-labeling if and only if \(k \leq 4\).