Turán theorems with repeated degrees
type: Item
instance of: scholarly article
title: Turán theorems with repeated degrees
zbMATH Open document ID: 0765.05053
DOI: 10.1016/0012-365X(92)90644-U
author: Michael O. Albertson
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: Let \(s_ q(n)\) denote the maximum number of edges in a graph with \(n\) vertices and no \(K_{q+1}\) in which all vertices have the same degree. This paper determines \(s_ q(n)\) asymptotically, exhibits the extremal graphs (complete multipartite graphs) in certain cases, exhibits almost extremal graphs in the remaining cases, and investigates how far the almost extremal graphs are from being extremal. The case when \(q=1\) contains all of the essentials. The work was inspired by the following result of the author. If \(G\) is any graph with at least 6 vertices, then either \(G\) or \(G^ c\) contains a \(K_ 3\) in which two vertices have the same degree.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05A16
zbMATH DE Number: 90261
zbMATH Keywords: Turán theorems
zbMATH Keywords: maximum number of edges
zbMATH Keywords: degree
zbMATH Keywords: extremal graphs
MaRDI profile type: Publication
cites work: People Who Know People
cites work: Q3852212
cites work: Q3312262
description: scientific article; zbMATH DE number 90261