Bertrandʹs postulate, the prime number theorem and product anti-magic graphs Original Research Article

Let the edges of a finite simple graph image, be labeled by image. Denote by image the product of all the labels of edges incident with a vertex image. The graph G is called product anti-magic if it is possible that the above labeling results in all values image 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 image. In this paper we prove this conjecture for dense graphs, complete multi-partite graphs and some other families of graphs.