Equating two maximum degrees

Publication date 13 February 2019

Abstract: Given a graph

G

, 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 s q r t n

vertices, but the question if

2 s q r t n

is best possible remains open. Among the results obtained in this paper we prove that: 1. For every graph

G

on

n g e q 4

vertices we can delete at most

l c e i l f r a c - 3 + s q r t 8 n - 15 2 c e i l

vertices to get an induced subgraph

H

with at least two vertices realizing

D e l t a (H)

, and this bound is sharp, solving the problems left open by Caro and Yuster. 2.For every graph

G

with maximum degree

D e l t a g e q 1

we can delete at most

l c e i l f r a c - 3 + s q r t 8 D e l t a + 1 2 c e i l

vertices to get an induced subgraph

H

with at least two vertices realizing

D e l t a (H)

, and this bound is sharp. 3. Every graph

G

with

D e l t a (G) l e q 2

and least

2 k - 1

vertices (respectively

2 k - 2

vertices if k is even) contains an induced subgraph

H

in which at least

k

vertices realise

D e l t a (H)

, and these bound are sharp.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Equating two maximum degrees