Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651077 | Discrete Mathematics | 2007 | 8 Pages |
Abstract
Let SnSn denote the graph on {1,…,n}{1,…,n} in which two numbers are adjacent if and only if they are coprime. Around 1980 Entringer conjectured that SnSn contains every tree of order n as a subgraph.Here we show that this conjecture is true for all n⩽50n⩽50. Further positive evidence is provided by our main result that SnSn contains every tree of order (1-o(1))n(1-o(1))n.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Oleg Pikhurko,