Premium
Extremal graphs for the k ‐flower
Author(s) -
Yuan LongTu
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22237
Subject(s) - combinatorics , mathematics , lemma (botany) , graph , vertex (graph theory) , induced subgraph , discrete mathematics , botany , poaceae , biology
The Turán number of a graph H , e x ( n , H ) , is the maximum number of edges in any graph of order n that does not contain an H as a subgraph. A graph on 2 k + 1 vertices consisting of k triangles that intersect in exactly one common vertex is called a k ‐fan, and a graph consisting of k cycles that intersect in exactly one common vertex is called a k ‐flower. In this article, we determine the Turán number of any k ‐flower containing at least one odd cycle and characterize all extremal graphs provided n is sufficiently large. Erdős, Füredi, Gould, and Gunderson determined the Turán number for the k ‐fan. Our result is a generalization of their result. The addition aim of this article is to draw attention to a powerful tool, the so‐called progressive induction lemma of Simonovits.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom