Large induced subgraphs with k vertices of almost maximum degree

Abstract: In this note we prove that for every integer

k

, there exist constants

g_{1} (k)

and

g_{2} (k)

such that the following holds. If

G

is a graph on

n

vertices with maximum degree

D e l t a

then it contains an induced subgraph

H

on at least

n - g_{1} (k) s q r t D e l t a

vertices, such that

H

has

k

vertices of the same degree of order at least

D e l t a (H) - g_{2} (k)

. This solves a conjecture of Caro and Yuster up to the constant

g_{2} (k)

.

Recommendations

Cites Work

Cited In (10)

This page was built for publication: Large induced subgraphs with \(k\) vertices of almost maximum degree