Robertson, Leanne; Small, Ben On Newman’s conjecture and prime trees. (English) Zbl 1186.11003 Integers 9, No. 2, Article A10, 117-128 (2009). Summary: In 1980, C. Pomerance and J. L. Selfridge [Mathematika 27, 69–83 (1980; Zbl 0442.10003)] proved D. J. Newman’s coprime mapping conjecture: If \(n\) is a positive integer and \(I\) is a set of \(n\) consecutive integers, then there is a bijection \(f: \{1,2,\dots,n\}\to I\) such that \(\gcd(i, f(i))=1\) for \(1\leq i\leq n\). The function \(f\) described in their theorem is called a coprime mapping. Around the same time, R. Entringer conjectured that all trees are prime; that is, that if \(T\) is a tree with vertex set \(V\), then there is a bijection \(L: V \to \{1, 2, \ldots, |V|\}\) such that \(\gcd(L(x),L(y))=1\) for all adjacent vertices \(x\) and \(y\) in \(V\). So far, little progress towards a proof of this conjecture has been made. In this paper, we extend Pomerance and Selfridge’s theorem by replacing \(I\) with a set \(S\) of \(n\) integers in arithmetic progression and determining when there exist coprime mappings \(f:\{1,2,\dots,n\}\to S\) and \(g:\{1,3,\dots,2n-1\}\to S\).We devote the rest of the paper to using coprime mappings to prove that various families of trees are prime, including palm trees, banana trees, binomial trees, and certain families of spider colonies. Cited in 5 Documents MSC: 11A07 Congruences; primitive roots; residue systems 11B25 Arithmetic progressions 05C05 Trees 05C78 Graph labelling (graceful graphs, bandwidth, etc.) Citations:Zbl 0442.10003 PDFBibTeX XMLCite \textit{L. Robertson} and \textit{B. Small}, Integers 9, No. 2, Article A10, 117--128 (2009; Zbl 1186.11003) Full Text: DOI EuDML Link