α-Labelings and the Structure of Trees with Nonzero α-Deficit
Gunnar Brinkmann, Simon Crevals, Hadrien M\élot, Leanne Rylands, Eckhard Steffen
Abstract
We present theoretical and computational results on
α-labelings of trees. The theorems proved in this
paper were inspired by the results of a computer investigation of
α-labelings of all trees with up to 26 vertices,
all trees with maximum degree 3 and up to 36
vertices, all trees with maximum degree 4 and up to
32 vertices and all trees with maximum degree
5 and up to 31 vertices. We generalise a
criterion for trees to have nonzero α-deficit, and
prove an unexpected result on the α-deficit of
trees with a vertex of large degree compared to the order of the tree.
Full Text: PDF PostScript