pith. sign in

arxiv: 1511.07274 · v1 · pith:CNXSE4CDnew · submitted 2015-11-23 · 🧮 math.CO

The number of trees in a graph

classification 🧮 math.CO
keywords leastdegreegraphcopiesedgesisomorphiclabeledminimum
0
0 comments X
read the original abstract

Let $T$ be a tree with $t$ edges. We show that the number of isomorphic (labeled) copies of $T$ in a graph $G = (V,E)$ of minimum degree at least $t$ is at least \[2|E| \prod_{v \in V} (d(v) - t + 1)^{\frac{(t-1)d(v)}{2|E|}}.\] Consequently, any $n$-vertex graph of average degree $d$ and minimum degree at least $t$ contains at least $$nd(d-t+1)^{t-1}$$ isomorphic (labeled) copies of $T$. This answers a question of Dellamonica et. al. (where the above statement was proved when $T$ is the path with three edges) while extending an old result of Erd\H os and Simonovits.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.