Bertrand's postulate, the prime number theorem and product anti-magic graphs

Let the edges of a finite simple graph G=(V,E),|V|=n,|E|=mG=(V,E),|V|=n,|E|=m, be labeled by 1,2,…,m1,2,…,m. Denote by w(u)w(u) the product of all the labels of edges incident with a vertex uu. The graph G is called product anti-magic   if it is possible that the above labeling results in all values w(u)w(u) being distinct.Following an old conjecture of Hartsfield and Ringel on (sum) anti-magic graphs (see [N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Inc., Boston, 1990, pp. 108–109 (revised version, 1994)]), Figueroa-Centeno et al. [Bertrand's postulate and magical product labellings, Bull. ICA 30 (2000) 53–65] conjectured that every connected graph of size m is product anti-magic iff  m⩾3m⩾3. In this paper we prove this conjecture for dense graphs, complete multi-partite graphs and some other families of graphs.