The Turán number of the square of a path

DOI10.1016/J.DAM.2021.10.003MaRDI QIDQ2057579zbMATH OpenOpenAlexFDO

Authors Chuanqi Xiao, Oscar Zamora, Ji Meng Xiao, Gyula O. H. Katona

Publication date 7 December 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

extremal graphssquare of a pathTurán number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30)

Abstract: The Tur'an 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. Let P_k be the path with k vertices, the square P^2_k of P_k is obtained by joining the pairs of vertices with distance one or two in P_k. The powerful theorem of ErdH{o}s, Stone and Simonovits determines the asymptotic behavior of ex(n,P^2_k). In the present paper, we determine the exact value of ex(n,P^2_5) and ex(n,P^2_6) and pose a conjecture for the exact value of ex(n,P^2_k).

Recommendations

• The Turán number of disjoint copies of paths
• The Turań number of \(2P_7\)
• A proof for a conjecture of Gorgol
• Turán numbers of multiple paths and equibipartite forests
• Turán numbers for disjoint paths

Cites work

• scientific article; zbMATH DE number 3652374 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• Extensions of Turán's theorem on graphs
• Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions
• Extremal graphs for blow-ups of cycles and trees
• Extremal graphs for intersecting triangles
• Extremal numbers for odd cycles
• On maximal paths and circuits of graphs
• On the structure of linear graphs
• Path Ramsey numbers in multicolorings

Cited in

(7)

• Paths are Turán-good
• Extremal graphs of the \(p\)th power of paths
• A spectral condition for the existence of the square of a path
• Extremal graphs for the odd prism
• Generalized Turán numbers for the edge blow-up of a graph
• Turán numbers for disjoint paths
• A short derivation for Turán numbers of paths

This page was built for publication: The Turán number of the square of a path

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