The Turán number of the square of a path

2019/12/05 by Chuanqi Xiao, Xiao, Chuanqi, Gyula O. H. Katona +5 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · doi:10.48550/arxiv.1912.02726

openalex publication_date 2019/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Turán 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²_k of P_k is obtained by joining the pairs of vertices with distance one or two in P_k. The powerful theorem of Erdős, Stone and Simonovits determines the asymptotic behavior of ex(n,P²_k). In the present paper, we determine the exact value of ex(n,P²₅) and ex(n,P²₆) and pose a conjecture for the exact value of ex(n,P²_k).

Cited by

• Turán number of four vertex-disjoint cliques
• How to find all extremal graphs using symmetric subgraphs
• Spectral extremal problem of the pth power of cycles

Related

• Turán numbers for disjoint paths
• The Turan Number of Disjoint Copies of Paths
• Generalized Turán problem for a path and a clique
• Extremal graphs without long paths and a given graph
• Some results on the Turán number of k₁P_ℓ∪ k₂S_ℓ-1