Branching Extent and Spectra of Trees


Milosz Michalski


Following the concepts of Ruch and Gutman [7] we discuss possible connections between branching extent and spectra of trees. It is suggested to what extent relations between spectra reflect partial ordering of trees according to their branching. We show how branching can be measured by certain coefficients of characteristic polynomial of a tree. The second part of the paper is devoted to the problem of constructing trees with a fixed measure of branching. A non-polynomial time algorithm is developed and its acceptably good performance in the majority of cases is documented by sample computation results.