On the Turán Number of Generalized Theta Graphs

2021/03/18 by Xiao‐Chuan Liu, Yang Xu, Liu, Xiao-Chuan +1 · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Graph theory and applications #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2103.10200

Abstract

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

Cited by

• Non-bipartite graphs without theta subgraphs

Related

• Turán numbers of theta graphs
• Counting cliques without generalized theta graphs
• The Random Turán Problem for Theta Graphs
• Generalized Turán problem for a path and a clique
• Some results on the Turán number of k₁P_ℓ∪ k₂S_ℓ-1