Counting Trees in Graphs

Electronic Journal Of Combinatorics

Jacques Verstraete¹ 

关键词: Embedding trees;    Paths;    Random embedding;    Jensen';    s Inequality;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

Erdős and Simonovits proved that the number of paths of length $t$ in an $n$-vertex graph of average degree $d$ is at least $(1 - \delta) nd(d - 1) \cdots (d - t + 1)$, where $\delta = (\log d)^{-1/2 + o(1)}$ as $d \rightarrow \infty$. In this paper, we s

【 授权许可】

Others