On the longest simple path in the divisor graph. (English) Zbl 0546.05038

Pomerance, Carl

Combinatorics, graph theory and computing, Proc. 14th Southeast. Conf., Boca Raton/Flo. 1983, Congr. Numerantium 40, 291-304 (1983).

[For the entire collection see Zbl 0523.00001.]
Let f(n) denote the length of the longest path in the graph whose vertices are the numbers 1,2,...,n and in which two distinct vertices are adjacent if one of the corresponding numbers divides the other. The author shows that \(f(n)=o(n)\) as \(n\to\infty.\)

Reviewer: J.W.Moon

MSC:

05C38	Paths and cycles
11N05	Distribution of primes

Keywords:

path length; divisor graph

Citations:

Zbl 0523.00001