M. Fürst, M. Gentner, M.A. Henning, S. Jäger, D. Rautenbach
Equating k maximum degrees in graphs without short cycles
Discussiones Mathematicae Graph Theory
Received 29.11.2017, Revised 15.05.2018, Accepted 15.05.2018, doi: 10.7151/dmgt.2152

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)≤ ck \sqrt{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 \frac{1}{6}(t3+6t2+17t+12), 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)\frac{p+1}{3p}). Finally, we show that, for every fixed k, and every given forest F, the value of fk(F) can be determined in polynomial time.
maximum degree, repeated degrees, repetition number