Outerplanar Turán number of a cycle

2023/10/01 by Ervin Győri, Győri, Ervin, Guilherme Zeus Dantas e Moura +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2310.00557

openalex publication_date 2023/10/01 · openalex created_date 2023/10/04 · openalex updated_date 2026/07/28

Abstract

A graph is outerplanar if it has a planar drawing for which all vertices belong to the outer face of the drawing. Let H be a graph. The outerplanar Turán number of H, denoted by ex_OP(n,H), is the maximum number of edges in an n-vertex outerplanar graph which does not contain H as a subgraph. In 2021, L. Fang et al. determined the outerplanar Turán number of cycles and paths. In this paper, we use techniques of dual graph to give a shorter proof for the sharp upperbound of ex_OP(n,C_k)≤ ((2k - 5)(kn - k - 1))/(k² - 2k - 1).

Related

• Outerplanar Turán numbers of cycles and paths
• Generalized outerplanar Turán number of short paths
• The planar Turán number of the seven-cycle
• An improved lower bound for the planar Turán number of cycles
• Generalized Outerplanar Turán numbers and maximum number of k-vertex subtrees