Forcing \(k\)-repetitions in degree sequences
The electronic journal of combinatorics, Tome 21 (2014) no. 1
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.
@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/}
}
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
Cité par Sources :