{
  "id": "2401.00807",
  "version": "v1",
  "published": "2024-01-01T16:30:03.000Z",
  "updated": "2024-01-01T16:30:03.000Z",
  "title": "An infinite family of counterexamples to a conjecture on distance magic labeling",
  "authors": [
    "Ehab Ebrahem",
    "Shlomo Hoory",
    "Dani Kotlar"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "This work is about a partition problem which is an instance of the distance magic graph labeling problem. Given positive integers $n,k$ and $p_1\\le p_2\\le \\cdots\\le p_k$ such that $p_1+\\cdots+p_k=n$ and $k$ divides $\\sum_{i=1}^ni$, we study the problem of characterizing the cases where it is possible to find a partition of the set $\\{1,2,\\ldots,n\\}$ into $k$ subsets of respective sizes $p_1,\\dots,p_k$, such that the element sum in each subset is equal. Using a computerized search we found examples showing that the necessary condition, $\\sum_{i=1}^{p_1+\\cdots+p_j} (n-i+1)\\ge j{\\binom{n+1}{2}}/k$ for all $j=1,\\ldots,k$, is not generally sufficient, refuting a past conjecture. Moreover, we show that there are infinitely many such counter-examples. The question whether there is a simple characterization is left open and for all we know the corresponding decision problem might be NP-complete.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-01-01T16:30:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "distance magic labeling",
      "infinite family",
      "conjecture",
      "counterexamples",
      "distance magic graph labeling problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}