2017/05/21 by M. Fürst, Maximilian Fürst, M. Gentner +12 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1705.07409
arxiv created 2017/05/21 · openalex publication_date 2017/05/21 · arxiv updated 2017/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 √(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 (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)(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.