×

On Newman’s conjecture and prime trees. (English) Zbl 1186.11003

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.

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
Full Text: DOI EuDML Link