Equating maximum degrees in graphs without short cycles

Abstract: For an integer

k

at least

2

, and a graph

G

, let

f_{k} (G)

be the minimum cardinality of a set

X

of vertices of

G

such that

G - X

has either

k

vertices of maximum degree or order less than

k

. Caro and Yuster (Discrete Mathematics 310 (2010) 742-747) conjectured that, for every

k

, there is a constant

c_{k}

such that

f_{k} (G) l e q c_{k} s q r t n (G)

for every graph

G

. Verifying a conjecture of Caro, Lauri, and Zarb (arXiv:1704.08472v1), we show the best possible result that, if

t

is a positive integer, and

F

is a forest of order at most

f r a c 16 l e f t (t^{3} + 6 t^{2} + 17 t + 12 i g h t)

, then

f_{2} (F) l e q t

. We study

f_{3} (F)

for forests

F

in more detail obtaining similar almost tight results, and we establish upper bounds on

f_{k} (G)

for graphs

G

of girth at least

5

. For graphs

G

of girth more than

2 p

, for

p

at least

3

, our results imply

f_{k} (G) = O l e f t (n (G)^{f r a c p + 1 3 p} i g h t)

. Finally, we show that, for every fixed

k

, and every given forest

F

, the value of

f_{k} (F)

can be determined in polynomial time.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Equating \(\kappa\) maximum degrees in graphs without short cycles