On the Turan number of forests

2012/04/13 by Lidický, Bernard, Liu, Hong, Palmer, Cory · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1204.3102

Abstract

The Turan number of a graph H, ex(n,H), is the maximum number of edges in a graph on n vertices which does not have H as a subgraph. We determine the Turan number and find the unique extremal graph for forests consisting of paths when n is sufficiently large. This generalizes a result of Bushaw and Kettle [ Combinatorics, Probability and Computing 20:837--853, 2011]. We also determine the Turan number and extremal graphs for forests consisting of stars of arbitrary order.

Cited by

• Turán type problems for a fixed graph and a linear forest

Related

• The Turán number of path-star forests
• Turán numbers for disjoint paths
• Turán numbers for hypergraph star forests
• Some results on the Turán number of k₁P_ℓ∪ k₂S_ℓ-1
• The Turán number of k₁P_2l∪ k₂S_2l-1