Timeline for Term or reference for a set of integer edge weights to guarantee distinct weighted degrees
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 10, 2021 at 18:41 | history | edited | subset | CC BY-SA 4.0 |
Included wording suggested in comments
|
| Feb 10, 2021 at 18:30 | comment | added | Louis D | I see. Can a suggest a alternate phrasing: You are looking to minimize the largest element in a set $S$ of $\binom{n}{2}$ non-negative integers having the property that for every bijection $w:E(K_n)\to S$ and every pair of distinct vertices $u,v\in V(K_n)$, we have $\sum_{e\ni v}w(e)\neq \sum_{e\ni u}w(e)$. | |
| Feb 10, 2021 at 18:26 | comment | added | subset | @LouisD I've tried to clarify the question. I'm interested in a set of labels that ensures, no matter how you arrange the labels on the $K_n$, that the network will still be irregular. That is, the labels should work for all assignments, not just one. Sorry for the poor wording before. | |
| Feb 10, 2021 at 18:23 | history | edited | subset | CC BY-SA 4.0 |
Distinguished from irregularity strength
|
| Feb 10, 2021 at 18:14 | history | edited | subset | CC BY-SA 4.0 |
Started clarification
|
| Feb 10, 2021 at 18:09 | comment | added | Louis D | 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? | |
| Feb 10, 2021 at 17:57 | comment | added | subset | 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. | |
| Feb 10, 2021 at 17:55 | comment | added | subset | @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. | |
| Feb 10, 2021 at 17:44 | comment | added | Louis D | 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 | |
| Feb 10, 2021 at 16:33 | comment | added | Louis D | 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. | |
| Feb 10, 2021 at 15:33 | review | First posts | |||
| Feb 10, 2021 at 15:53 | |||||
| Feb 10, 2021 at 15:28 | history | asked | subset | CC BY-SA 4.0 |