HOW TO MAKE A RANDOM GRAPH IRREGULAR

An irregular edge labeling of a graph G = (V, E) is a weight assignmen t f: E --> N such that the sums f(+)(v):= Sigma(v is an element of e i s an element of e is an element of E) f(e) are pairwise distinct. If s uch labelings exist in G, then the value of min(f) Sigma(e is an eleme nt of 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 n(2)/4 + o(n (2)) as n --> infinity, whenever p(n). n(2/3) --> infinity. This asymp totic result is deduced from a general estimate (valid for every graph ) involving vertex degrees and the size of largest triangle packings. (C) 1995 John Wiley & Sons, Inc.