Generalized degree polynomials of trees

Abstract

The generalized degree polynomial ${\mathbf{G}}_T(x,y,z)$ of a tree $T$ is an invariant introduced by Crew that enumerates subsets of vertices by size and number of internal and boundary edges. Aliste-Prieto et al. proved that ${\mathbf{G}}_T$ is determined linearly by the chromatic symmetric function ${\mathbf{X}}_T$, introduced by Stanley. We present several classes of information about $T$ that can be recovered from ${\mathbf{G}}_T$ and hence also from ${\mathbf{X}}_T$. Examples of such information include the double-degree sequence of $T$, which enumerates edges of $T$ by the pair of degrees of their endpoints, and the leaf adjacency sequence of $T$, which enumerates vertices of $T$ by degree and number of adjacent leaves. We also discuss a further generalization of ${\mathbf{G}}_T$ that enumerates tuples of vertex sets and show that this is also determined by ${\mathbf{X}}_T$.

19 pages, 3 figures; added remarks following proof of Prop 2.4