Sizes of graphs with induced subgraphs of large maximum degree
type: Item
instance of: scholarly article
title: Sizes of graphs with induced subgraphs of large maximum degree
zbMATH Open document ID: 0858.05057
DOI: 10.1016/0012-365X(95)00008-K
author: Talmage James Reid
author: William Staton
author: R. H. Schelp
author: P. Erdős
published in: Discrete Mathematics
publication date: 1997-03-23T00:00:00Z
review text: The following conjecture is considered: Let \(n\geq k\geq j\geq 1\) and \(n\geq 3\), let \(G\) be a graph with \(n+k\) vertices in which every \(n+j\) vertices induce a subgraph which contains a vertex of degree at least \(n\). Then \(G\) has at least \((k-j+1)n+\binom{k-j+1}{2}\) edges. The authors prove that this conjecture holds for \(j\geq 2\) and \(n\geq \max\{j(k-j),\binom{k-j+2}{2}\}\).
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 943235
zbMATH Keywords: minimum degree
zbMATH Keywords: induced subgraph
Wikidata QID: Q105518496
MaRDI profile type: Publication
cites work: SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY
cites work: Q5688994
full work available at URL: 0012-365x(95)00008-k
OpenAlex ID: W1994335179
description: scientific article; zbMATH DE number 943235