On the roots of the subtree polynomial

DOI10.1016/J.EJC.2020.103181MaRDI QIDQ2198997zbMATH OpenOpenAlexFDO

Authors Jason I. Brown, L. A. S. Mól

Publication date 15 September 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.08655

zbMATH Keywords

subtree roots

Mathematics Subject Classification ID

Trees (05C05) Graph polynomials (05C31)

Abstract: For a tree $T$, the subtree polynomial of $T$ is the generating polynomial for the number of subtrees of $T$. We show that the complex roots of the subtree polynomial are contained in the disk $leftzinmathbbCcolon|z|leq1+sqrt[3]3ight$, and that $K_{1,3}$ is the only tree whose subtree polynomial has a root on the boundary. We also prove that the closure of the collection of all real roots of subtree polynomials contains the interval $[-2,-1]$, while the intervals $(infty,-1-sqrt[3]3)$, $[-1,0)$, and $(0,infty)$ are root-free.

Recommendations

• scientific article; zbMATH DE number 3849252
• On the roots of chromatic polynomials
• Tutte polynomials for trees
• On roots of Wiener polynomials of trees
• On the number of nonisomorphic subtrees of a tree

Cites work

• A course in mathematical analysis. Volume 1: Foundations and elementary real analysis
• Alternating Whitney sums and matchings in trees. 1
• Alternating Whitney sums and matchings in trees. II
• Enumeration of subtrees of trees
• Extremal results on average subtree density of series-reduced trees
• scientific article; zbMATH DE number 568836 (Why is no real title available?)
• scientific article; zbMATH DE number 2199828 (Why is no real title available?)
• Indistinguishable trees and graphs
• Maximizing the mean subtree order
• Monotonicity of the mean order of subtrees
• On the average number of nodes in a subtree of a tree
• On the distribution of subtree orders of a tree
• On the local and global means of subtree orders
• On the roots of all-terminal reliability polynomials
• On the roots of domination polynomials
• On the roots of edge cover polynomials of graphs
• On the roots of the node reliability polynomial
• The average order of a subtree of a tree
• The minimal number of subtrees of a tree
• The minimal number of subtrees with a given degree sequence
• The number of subtrees of trees with given degree sequence

Cited in

(6)

• Counting unbranched subgraphs
• A combinatorial interpretation of the Conti-Contucci-Falcolini polynomial
• The ratio of the numbers of odd and even cycles in outerplanar graphs
• Structure Polynomials and Subgraphs of Rooted Regular Trees
• scientific article; zbMATH DE number 7583268 (Why is no real title available?)
• Models of random subtrees of a graph

This page was built for publication: On the roots of the subtree polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2198997)