Search

The extremal number ex (n , F) of a graph F is the maximum number of edges in an n -vertex graph not containing F as a subgraph. A real number r ∈ [ 1 , 2 ] is realisable if there exists a graph F with ex (n , F) = Θ (n r). Several decades ago, Erdős and Simonovits conjectured that every rational number in [ 1 , 2 ] is realisable. Despite decades of effort, the only known realisable numbers are 0 , 1 , 7 5 , 2 , and the numbers of the form 1 + 1 m , 2 − 1 m , 2 − 2 m for integers m ≥ 1. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than the two numbers 1 and 2. In this paper, we make progress on the conjecture of Erdős and Simonovits. First, we show that 2 − a b is realisable for any integers a , b ≥ 1 with b > a and b ≡ ± 1 (mod a). This includes all previously known ones, and gives infinitely many limit points 2 − 1 m in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable. [ABSTRACT FROM AUTHOR]

For graphs H and F with chromatic number χ (F) = k , we call H strictly F -Turán-good (or (H , F) strictly Turán-good) if the Turán graph T k − 1 (n) is the unique F -free graph on n vertices containing the largest number of copies of H when n is large enough. Let F be a graph with chromatic number χ (F) ≥ 3 and a color-critical edge and let P ℓ be a path with ℓ vertices. Gerbner and Palmer (2020) showed that (P 3 , F) is strictly Turán good if χ (F) ≥ 4 and they conjectured that (a) this result is true when χ (F) = 3 , and, moreover, (b) (P ℓ , K k) is Turán-good for every pair of integers ℓ and k. In the present paper, we show that (H , F) is strictly Turán-good when H is a bipartite graph with matching number ν (H) = ⌊ | V (H) | 2 ⌋ and χ (F) = 3 , as a corollary, this result confirms the conjecture (a); we also prove that (P ℓ , F) is strictly Turán-good for 2 ≤ ℓ ≤ 6 and χ (F) ≥ 4 , this also confirms the conjecture (b) for 2 ≤ ℓ ≤ 6 and k ≥ 4. [ABSTRACT FROM AUTHOR]

A graph Γ is said to be distance-balanced if for any edge u v of Γ , the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u , and it is called nicely distance-balanced if in addition this number is independent of the chosen edge u v. A graph Γ is said to be strongly distance-balanced if for any edge u v of Γ and any integer k , the number of vertices at distance k from u and at distance k + 1 from v is equal to the number of vertices at distance k + 1 from u and at distance k from v. In this paper we solve an open problem posed by Kutnar and Miklavič (2014) by constructing several infinite families of nonbipartite nicely distance-balanced graphs which are not strongly distance-balanced. We disprove a conjecture regarding characterization of strongly distance-balanced graphs posed by Balakrishnan et al. (2009) by providing infinitely many counterexamples, and answer a question posed by Kutnar et al. in (2006) regarding the existence of semisymmetric distance-balanced graphs which are not strongly distance-balanced by providing an infinite family of such examples. We also show that for a graph Γ with n vertices and m edges it can be checked in O (m n) time if Γ is strongly-distance balanced and if Γ is nicely distance-balanced. [ABSTRACT FROM AUTHOR]