1
$\begingroup$

I am looking for a term or reference describing sets $S$ of $\binom{n}{2}$ non-negative integers such that, for every bijection $w: E(K_n)\to S$ and every pair of distinct vertices $u$ and $v$ in $V(K_n)$, $\sum_{e\ni u}w(e)\ne\sum_{e\ni v}w(e)$, ideally a reference describing bounds on the largest element of such an $S$ when given $n$. Equivalently, since any two vertices in a $K_n$ share an edge, I am looking for a term or reference about sets of $\binom{n}{2}$ integers such that every subset of size $n-2$ has a distinct sum.

For example, if the ten edges of a $K_5$ are weighted with the integers $\{0, 1, 2, 22, 42, 60, 84, 98, 108, 113\}$, then regardless of which edges take which weights, the sum of the incident edge weights at each vertex must be distinct. Or, put another way, all of the triples drawn from this set have distinct sums.

The concept of irregularity strength is close. But it describes the range of integers needed to allow an irregular assignment, not to guarantee it. For example, if a $K_5$ has the weights $1, 1, 1, 1, 1, 1, 2, 2, 2, 3$, then those weights can be arranged to give its vertices distinct weighted degrees, but the weights can still be assigned so that two weighted degrees are equal.

Unfortunately, my searches through the literature have not been very helpful because I keep turning up papers on sets where all subsets have distinct sums—a stronger condition that gives poor bounds for my current case. Likewise, I have not had success searching the OEIS.

Is there any work about sets satisfying this weaker condition?

$\endgroup$
7
  • $\begingroup$ I think you are looking for "irregularity strength." It is conjectured that the set {1,2,3} suffices and it is known that {1,2,3,4,5} suffices, but perhaps the conjecture is known for complete graphs. $\endgroup$
    – Louis D
    Commented Feb 10, 2021 at 16:33
  • $\begingroup$ Sure, I can do that. Perhaps after you dig into it, you can comment on my answer whether the 1-2-3 conjecture is known for complete graphs. I did see a recent paper which shows that for regular graphs the set {1,2,3,4} suffices. "The 1–2–3 Conjecture almost holds for regular graphs" by Pryzbylo $\endgroup$
    – Louis D
    Commented Feb 10, 2021 at 17:44
  • $\begingroup$ @LouisD First off, doi.org/10.1016/0012-365X(94)E0043-H claims "there are several proofs", so apparently it is known for complete graphs. $\endgroup$
    – subset
    Commented Feb 10, 2021 at 17:55
  • $\begingroup$ And thank you for making an answer. But I wasn't thinking, and the quantifier is wrong: I want a set that guarantees an irregular network, not one that just permits it. I at least have a starting point though, so if I get anywhere from the lead you gave, I'll accept the answer with a comment. $\endgroup$
    – subset
    Commented Feb 10, 2021 at 17:57
  • $\begingroup$ I see. When you said "a set of $\binom{n}{2}$ integers" I wrongly interpreted that as "at most $\binom{n}{2}$ integers." So just to clarify, you want an irregular edge labeling with distinct non-negative integers and you want to minimize the largest weight? $\endgroup$
    – Louis D
    Commented Feb 10, 2021 at 18:09

0

You must log in to answer this question.