- Tytuł:
- Equating κ Maximum Degrees in Graphs without Short Cycles
- Autorzy:
-
Fürst, Maximilian
Gentner, Michael
Jäger, Simon
Rautenbach, Dieter
Henning, Michael A. - Powiązania:
- https://bibliotekanauki.pl/articles/31523205.pdf
- Data publikacji:
- 2020-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
maximum degree
repeated degrees
repetition number - Opis:
- 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 \(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\bigg(n(G)\frac{p+1}{3_p}\bigg)\). 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 841-853
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł