Forcing \(k\)-repetitions in degree sequences
The electronic journal of combinatorics, Tome 21 (2014) no. 1
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl arXiv
One of the most basic results in graph theory states that every graph with at least two vertices has two vertices with the same degree. Since there are graphs without $3$ vertices of the same degree, it is natural to ask if for any fixed $k$, every graph $G$ is "close" to a graph $G'$ with $k$ vertices of the same degree. Our main result in this paper is that this is indeed the case. Specifically, we show that for any positive integer $k$, there is a constant $C=C(k)$, so that given any graph $G$, one can remove from $G$ at most $C$ vertices and thus obtain a new graph $G'$ that contains at least $\min\{k,|G|-C\}$ vertices of the same degree.Our main tool is a multidimensional zero-sum theorem for integer sequences, which we prove using an old geometric approach of Alon and Berman.
Yair Caro; Asaf Shapira; Raphael Yuster. Forcing \(k\)-repetitions in degree sequences. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/3503
@article{10_37236_3503,
author = {Yair Caro and Asaf Shapira and Raphael Yuster},
title = {Forcing \(k\)-repetitions in degree sequences},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/3503},
zbl = {1300.05064},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3503/}
}
Cité par Sources :