Two extremal problems in graph theory
type: Item
instance of: scholarly article
title: Two extremal problems in graph theory
zbMATH Open document ID: 0810.05041
author: Richard A. Brualdi
author: Stephen Mellendorf
published in: The Electronic Journal of Combinatorics
publication date: 1995-02-12T00:00:00Z
full work available at URL: https://eudml.org/doc/118558
full work available at URL: R2
review text: 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\).
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 721221
zbMATH Keywords: extremal problems
zbMATH Keywords: maximum number of edges
MaRDI profile type: Publication
Recommended article: Q3699717
Recommended article: Q4726280
Recommended article: Q5610919
Recommended article: Q5543308
Recommended article: Q5728132
Recommended article: On some extremal problems in graph theory
Recommended article: Q5753977
Recommended article: Q3966172
Recommended article: An extremal problem in graph theory
description: scientific article; zbMATH DE number 721221