On the Turán number of forests

zbMATH Open1298.05071arXiv1204.3102MaRDI QIDQ396789FDOQ396789

Authors: Bernard Lidický, Cory Palmer, Hong Liu 

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1204.3102

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The Turán numbers of special forests
• The Turán number of star forests
• Turán numbers of multiple paths and equibipartite forests
• Generalized Turán number for linear forests
• Some new results on the Turán number of star forests

zbMATH Keywords

forestedges

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Cites Work

• Title not available (Why is that?)
• On maximal paths and circuits of graphs
• Title not available (Why is that?)
• On the structure of linear graphs
• Path Ramsey numbers in multicolorings
• Title not available (Why is that?)
• On Graphs that do not Contain a Thomsen Graph
• On a problem of K. Zarankiewicz
• Cycles of even length in graphs
• New asymptotics for bipartite Turán numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the theory of graphs
• Subtrees and subforests of graphs
• Turán numbers of multiple paths and equibipartite forests
• Embedding a forest in a graph
• Turán numbers for disjoint copies of graphs

Cited In (57)

• The Turán number of \(P_9 \cup P_7\)
• Connected Turán number of trees
• On the Turán numbers of linear forests in bipartite graphs
• Turán numbers of general star forests in hypergraphs
• How connectivity affects the extremal number of trees
• Extremal graphs for the suspension of edge-critical graphs
• Rainbow Turán problems for paths and forests of stars
• Turán numbers for hypergraph star forests
• The Turán number of star forests
• On the spectral radius of graphs without a star forest
• The Turán numbers of special forests
• The Turań number of \(2P_7\)
• On the anti-Ramsey number of forests
• The signless Laplacian spectral radius of graphs with forbidding linear forests
• An \(A_\alpha\)-spectral Erdős-Pósa theorem
• The Turán number of the graph 3P5
• An extremal result for subgraphs with few edges
• A note on the Turán number of an arbitrary star forest
• The Turán number of \(k \cdot S_\ell \)
• Some new results on the Turán number of star forests
• On Turán number for \(S_{\ell_1} \cup S_{\ell_2}\)
• Turán number for odd‐ballooning of trees
• Turán numbers of multiple paths and equibipartite forests
• On the \(A_\alpha\)-spectral radius of graphs without linear forests
• The Turán number of blow-ups of trees
• The Turán number for \(4 \cdot S_{\ell}^1\)
• Generalized Turán number of even linear forests
• Generalized Turán number for linear forests
• The formula for Turán number of spanning linear forests
• Two results about the Turán number of star forests
• On the Turán number of ordered forests
• A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
• Generalized Turán problems for disjoint copies of graphs
• On the Turán number of theta graphs
• Turán numbers for forests of paths in hypergraphs
• A proof for a conjecture of Gorgol
• The Turan number of graphs with given decomposition family
• The bipartite Turán number and spectral extremum for linear forests
• On extremal hypergraphs for forests of tight paths
• The complete value of the Turán number of \(3K_{p+1}\)
• On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees
• The Turán number for spanning linear forests
• The Turán number of disjoint copies of paths
• Turán numbers for disjoint paths
• The Turan number of \({P_5} \bigcup {P_9}\)
• Spectral radius conditions for the existence of all subtrees of diameter at most four
• Hypergraphs not containing a tight tree with a bounded trunk
• On zero-sum spanning trees and zero-sum connectivity
• On the anti-Ramsey numbers of linear forests
• A note on the Turán number of disjoint union of wheels
• Erdős-Gallai stability theorem for linear forests
• Turán's problem for trees
• Turán numbers of vertex-disjoint cliques in \(r\)-partite graphs
• Degree powers in graphs with a forbidden forest
• Anti-Ramsey numbers of paths and cycles in hypergraphs
• Spectral extremal results with forbidding linear forests
• The maximum number of stars in a graph without linear forest

This page was built for publication: On the Turán number of forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396789)