Equating κ Maximum Degrees in Graphs without Short Cycles

Abstract

For an integer k at least 2, and a graph G, let fk(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 ck such that fk(G)≤ckn(G){f_k}\left( G \right) \le {c_k}\sqrt {n\left( G \right)} 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 16(t3+6t2+17t+12){1 \over 6}\left( {{t^3} + 6{t^2} + 17t + 12} \right), then f2(F ) ≤ t. We study f3(F ) for forests F in more detail obtaining similar almost tight results, and we establish upper bounds on fk(G) for graphs G of girth at least 5. For graphs G of girth more than 2p, for p at least 3, our results imply fk(G)=O(n(G)p+13p){f_k}\left( G \right) = O\left( {n{{\left( G \right)}^{{{p + 1} \over {3p}}}}} \right) . Finally, we show that, for every fixed k, and every given forest F , the value of fk(F ) can be determined in polynomial time.

Keywords

• maximum degree
• repeated degrees
• repetition number
• 05c05
• 05c07