On the Turán Number of Theta Graphs

The Turán number ex ( n ,  H ) is the maximum number of edges in any graph of order n that contains no copy of H as a subgraph. For any three positive integers p ,  q ,  r with p ≤ q ≤ r and q ≥ 2 , let θ ( p , q , r ) denote the graph obtained from three internally disjoint paths with the same pair...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2021, Vol.37 (6), p.2155-2165
Main Authors: Zhai, Mingqing, Fang, Longfei, Shu, Jinlong
Format: Article
Language:English
Subjects:
Combinatorics
Engineering Design
Graph theory
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Turán number ex ( n ,  H ) is the maximum number of edges in any graph of order n that contains no copy of H as a subgraph. For any three positive integers p ,  q ,  r with p ≤ q ≤ r and q ≥ 2 , let θ ( p , q , r ) denote the graph obtained from three internally disjoint paths with the same pair of endpoints, where the three paths are of lengths p ,  q ,  r , respectively. Let k = p + q + r - 1 . In this paper, we obtain the exact value of e x ( n , θ ( p , q , r ) ) and characterize the unique extremal graph for n ≥ 9 k 2 - 3 k and any p ,  q ,  r with different parities. This extends a known result on odd cycles.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-021-02342-5