How to make a random graph irregular
Źsolt Tuza · Random Structures and Algorithms · 1995
Abstract An irregular edge labeling of a graph G = (V, E) is a weight assignment f: E→ N such that the sums f + (v):= Σv∈e∈E f(e) are pairwise distinct. If such labelings exist in G, then the value of minf Σe∈E (f(e) ‐ 1) measures the minimum number of edges needed to make G irregular. We prove that this minimum for the random graph G(n, p) with n vertices and edge probability p = p(n) is equal to n2/4 + o(n2) as n→∞, whenever p(n)‐n2/3→∞. This asymptotic result is deduced from a general estimate (valid for every graph) involving vertex degrees and the size of largest triangle packings. © 1995 John Wiley & Sons, Inc.