Geodesic
Equating κ Maximum Degrees in Graphs without Short Cycles
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 841-853.

Voir la notice de l'article provenant de la source Library of Science

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√(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(n(G)p+1/3_p). 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 
@article{DMGT_2020_40_3_a9,
     author = {F\"urst, Maximilian and Gentner, Michael and J\"ager, Simon and Rautenbach, Dieter and Henning, Michael A.},
     title = {Equating \ensuremath{\kappa} {Maximum} {Degrees} in {Graphs} without {Short} {Cycles}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {841--853},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a9/}
}
TY  - JOUR
AU  - Fürst, Maximilian
AU  - Gentner, Michael
AU  - Jäger, Simon
AU  - Rautenbach, Dieter
AU  - Henning, Michael A.
TI  - Equating κ Maximum Degrees in Graphs without Short Cycles
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 841
EP  - 853
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a9/
LA  - en
ID  - DMGT_2020_40_3_a9
ER  - 
%0 Journal Article
%A Fürst, Maximilian
%A Gentner, Michael
%A Jäger, Simon
%A Rautenbach, Dieter
%A Henning, Michael A.
%T Equating κ Maximum Degrees in Graphs without Short Cycles
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 841-853
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a9/
%G en
%F DMGT_2020_40_3_a9
Fürst, Maximilian; Gentner, Michael; Jäger, Simon; Rautenbach, Dieter; Henning, Michael A. Equating κ Maximum Degrees in Graphs without Short Cycles. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 841-853. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a9/

[1] M.O. Albertson and D.L. Boutin, Lower bounds for constant degree independent sets, Discrete Math. 127 (1994) 15–21. doi:10.1016/0012-365X(92)00463-2

[2] B. Bollobás and A.D. Scott, Independent sets and repeated degrees, Discrete Math. 170 (1997) 41–49. doi:10.1016/0012-365X(95)00355-Z

[3] Y. Caro, J. Lauri and C. Zarb, Equating two maximum degrees, manuscript. arXiv:1704.08472v1

[4] Y. Caro, A. Shapira and R. Yuster, Forcing k-repetitions in degree sequences, Electron. J. Combin. 21 (2014) #P24.

[5] Y. Caro and R. Yuster, Large induced subgraphs with equated maximum degree, Discrete Math. 310 (2010) 742–747. doi:10.1016/j.disc.2009.09.003

[6] Y. Caro and D.B. West, Repetition number of graphs, Electron. J. Combin. 16 (2009) #R7.

[7] M. Miller and J.Širáň, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin. 20 (2013) #DS14v2.