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\ge 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\le 4$.