ON A PROBLEM OF ERDOS ABOUT GRAPHS WHOSE SIZE IS THE TURAN NUMBER PLUS ONE

Authors：Qiao, Pu; Zhan, Xingzhi^*

Source：BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2022, 105(2): 177-187.

DOI：10.1017/S000497272100040X

• Turan number
• extremal graph theory
• Erdos problem
• book
• star
• 4-cycle

We consider finite simple graphs. Given a graph H and a positive integer n, the Turan number of H for the order n, denoted ex(n, H), is the maximum size of a graph of order n not containing H as a subgraph. Erd os asked: 'For which graphs H is it true that every graph on n vertices and ex(n, H) + 1 edges contains at least two H's? Perhaps this is always true.' We solve this problem in the negative by proving that for every integer k >= 4 there exists a graph H of order k and at least two orders n such that there exists a graph of order n and size ex(n, H) + 1 which contains exactly one copy of H. Denote by C-4 the 4-cycle. We also prove that for every integer n with 6 <= n <= 11 there exists a graph of order n and size ex(n, C-4) + 1 which contains exactly one copy of C-4, but, for n = 12 or n = 13, the minimum number of copies of C-4 in a graph of order n and size ex(n, C-4) + 1 is two.

• Institution
  华东理工大学