The Turán number of the square of a path

DOI10.1016/J.DAM.2021.10.003zbMATH Open1479.05159arXiv1912.02726OpenAlexW3210888381MaRDI QIDQ2057579FDOQ2057579

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)

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).

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

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

zbMATH Keywords

extremal graphssquare of a pathTurán number

Mathematics Subject Classification ID

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

Cites Work

• On maximal paths and circuits of graphs
• Title not available (Why is that?)
• On the structure of linear graphs
• Path Ramsey numbers in multicolorings
• Extremal graphs for intersecting triangles
• Extremal graphs for blow-ups of cycles and trees
• Title not available (Why is that?)
• Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions
• Extensions of Turán's theorem on graphs
• Extremal numbers for odd cycles

Cited In (7)

• Paths are Turán-good
• Extremal graphs of the \(p\)th power of paths
• Extremal graphs for the odd prism
• A spectral condition for the existence of the square of a path
• 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)