PC Seminar: Extremal trees with fixed degree sequence

Abstract: 
Joint work with Valisoa Razanajatovo Misanantenaina and Stephan G. Wagner. The so-called greedy tree G(D) and alternating greedy tree M(D) are known to be extremal graphs among elements of the set T_D of trees with degree sequence D, with respect to various graph invariants. This talk will discuss a generalized proof that covers a larger family of invariants for which G(D) or M(D) is an extremal graph in T_D. The result implies known results on the Wiener index, the number of subtrees, the number of independent subsets, the Hosoya index, the terminal Wiener index, and the energy of graphs. Furthermore, new results on the number of rooted spanning forests, the incidence energy and the solvability of a graph also follow. By comparing greedy trees, and alternating greedy trees, with different degree sequences, the results in T_D are extended to the set of trees whose degree sequences are majorized by D. 

No Zoom room for this seminar.

See upcoming seminars in our seminar series on Probability and Combinatorics (PC)