{
  "id": "1312.1213",
  "version": "v1",
  "published": "2013-12-04T15:43:26.000Z",
  "updated": "2013-12-04T15:43:26.000Z",
  "title": "Forcing $k$-repetitions in degree sequences",
  "authors": [
    "Yair Caro",
    "Asaf Shapira",
    "Raphael Yuster"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-12-04T15:43:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C07"
    ],
    "keywords": [
      "degree sequences",
      "repetitions",
      "graph theory states",
      "multidimensional zero-sum theorem",
      "old geometric approach"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1312.1213C"
    }
  }
}