Equating two maximum degrees

Abstract

Given a graph G and a positive integer k, we would like to find (if it exists) the largest induced subgraph H in which there are at least k vertices realizing the maximum degree of H. This problem was first posed by Caro and Yuster. They proved, for example, that for every graph G on n vertices we can guarantee, for k = 2, such an induced subgraph H by deleting at most 2√n vertices, but the question of whether 2√n is best possible remains open.