Two extremal problems in graph theory
Summary: We consider the following two problems. (1) Let \(t\) and \(n\) be positive integers with \(n\geq t\geq 2\). Determine the maximum number of edges of a graph of order \(n\) that contains neither \(K_ t\) nor \(K_{t,t}\) as a subgraph. (2) Let \(r\), \(t\) and \(n\) be positive integers with \(n\geq rt\) and \(t\geq 2\). Determine the maximum number of edges of a graph of order \(n\) that does not contain \(r\) disjoint copies of \(K_ t\). Problem 1 for \(n< 2t\) is solved by Turán's theorem and we solve it for \(n= 2t\). We also solve Problem 2 for \(n= rt\).
scientific article; zbMATH DE number 721221