On the Turán Number of Generalized Theta Graphs

Abstract

Let ${\Theta }_{k_1,\cdots ,k_{\ell }}$ denote the generalized theta graph, which consists of $\ell$ internally disjoint paths with lengths $k_1,\cdots ,k_{\ell }$, connecting two fixed vertices. We estimate the corresponding extremal number $\text{ex}(n,{\Theta }_{k_1,\cdots ,k_{\ell }})$. When the lengths of all paths have the same parity and at most one path has length 1, $\text{ex}(n,{\Theta }_{k_1,\cdots ,k_{\ell }})$ is $O(n^{1+1/k^{\ast }})$, where $2k^{\ast }$ is the length of the smallest cycle in ${\Theta }_{k_1,\cdots ,k_{\ell }}$. We also establish matching lower bound in the particular case of $\text{ex}(n,{\Theta }_{3,5,5})$.

References in corpus (2)

• A bound on the number of edges in graphs without an even cycle
• Graphs with few paths of prescribed length between any two vertices