An infinite family of counterexamples to a conjecture on distance magic labeling

preprint2024arXivOpen access

Abstract

This work is about a partition problem which is an instance of the distance magic graph labeling problem. Given positive integers n,kn,k and p1≤p2≤⋯≤pkp_1\le p_2\le \cdots\le p_k such that p1+⋯+pk=np_1+\cdots+p_k=n and kk divides ∑i=1ni\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,…,n}\{1,2,\ldots,n\} into kk subsets of respective sizes p1,…,pkp_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, ∑i=1p1+⋯+pj(n−i+1)≥j(n+12)/k\sum_{i=1}^{p_1+\cdots+p_j} (n-i+1)\ge j{\binom{n+1}{2}}/k for all j=1,…,kj=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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.