Turán numbers of theta graphs
Boris Bukh, Michael Tait
Abstract
Abstract The theta graph ${\Theta _{\ell ,t}}$ consists of two vertices joined by t vertex-disjoint paths, each of length $\ell $ . For fixed odd $\ell $ and large t , we show that the largest graph not containing ${\Theta _{\ell ,t}}$ has at most ${c_\ell }{t^{1 - 1/\ell }}{n^{1 + 1/\ell }}$ edges and that this is tight apart from the value of ${c_\ell }$ .
Topics & Concepts
CombinatoricsMathematicsDisjoint setsGraphVertex (graph theory)Discrete mathematicsLimits and Structures in Graph TheoryGraph theory and applicationsAdvanced Graph Theory Research