Authors: M. Fürst, M. Gentner, M.A. Henning, S. Jäger, D. Rautenbach Title: Equating k maximum degrees in graphs without short cycles Source: Discussiones Mathematicae Graph Theory Received 29.11.2017, Revised 15.05.2018, Accepted 15.05.2018, doi: 10.7151/dmgt.2152 | |
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)≤ c_{k} \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}(t^{3}+6t^{2}+17t+12), then f_{2}(F)≤ 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 2p, for p at least 3, our results imply f_{k}(G)=O(n(G)^{\frac{p+1}{3p}}). 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. | |
Keywords: maximum degree, repeated degrees, repetition number | |
Links: |