DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press

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: 2017-11-29, Revised: 2018-05-15, Accepted: 2018-05-15, https://doi.org/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)\leq 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}\left(t^3+6t^2+17t+12\right)$, then $f_2(F)\leq 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\left(n(G)^{\frac{p+1}{3p}}\right)$. 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