Forcing \(k\)-repetitions in degree sequences (Q405103)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Forcing \(k\)-repetitions in degree sequences |
scientific article |
Statements
Forcing \(k\)-repetitions in degree sequences (English)
0 references
4 September 2014
0 references
Summary: 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^\prime\) 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^\prime\) 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 \textit{N. Alon} and \textit{K. A. Berman} [J. Comb. Theory, Ser. A 43, 91--97 (1986; Zbl 0611.05044)].
0 references
degree sequence
0 references
repetition
0 references
subgraph
0 references
0 references