Bertrand's postulate, the prime number theorem and product anti-magic graphs (Q2470444): Difference between revisions

Let \(G\) denote a finite simple graph. Let \(c:E(G)\to\{1,2,\dots,m\}\) denote a function. For each vertex \(x\in V(G)\), let \(w(x)\) be the product of the images of the edges incident with \(x\), where \(w(x)=1\) if \(x\) is an isolated vertex. The graph \(G\) is \textit{product anti-magic} if a function \(c\) exists so that all the values \(w(x)\) are distinct. It has been conjectured by \textit{R. M. Figueroa-Centano, R. Ichishima} and \textit{F. A. Muntaner-Batle} [Bull. Inst. Comb. Appl. 30, 53--65 (2000; Zbl 0959.05103)] that a connected graph with \(m\) edges is product anti-magic if and only if \(m\geq3\). Assaults on this conjecture are made by showing that various conditions are sufficient for a graph \(G\) with \(n\) vertices and \(m\) edges to be product anti-magic. Among these conditions are the following: (1) \(G\) is a vertex-disjoint union of paths and cycles, each having \(\geq3\) edges; (2) \(G\) is connected, \(\epsilon>0\) is given, and \(m\geq(2+\epsilon)n\ln n\) for all sufficiently large \(n\); (3) there are no isolated vertices and the size \(\gamma\) of the smallest dominating set satisfies \(\gamma\leq m/(8\ln m)\); (4) there are no isolated vertices and either \(G\) is a complete \(k\)-partite graph (\(k\geq2\)) other than \(K_2\) or \(K_{1,2}\) or \(G\) is complete \(k\)-partite with \(k\geq3\).