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 alpha-labeling matrices. It is shown that each cornet S(k,q) admits no alpha-labelings whenever k > 4(q - 1) and q >= 2. We also give the sufficient conditions for the nonexistence of alpha-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 alpha-labeling if and only if k <= 4.