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

详细信息	查看全文 | 推荐本文 |

• 作者：G. Kaplan ; A. Lev ; Y. Roditty
• 关键词：Product anti-magic ; Labeling
• 刊名：Discrete Mathematics
• 出版年：2008
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：28 March 2008
• 卷：308
• 期：5-6
• 页码：787-794
• 文件大小：164 K

摘要

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