Least number of vertices in a graph with which one can uniquely recover some partition of N Given a partition of an integer N, its P-graph is the graph whose vertices are its parts, two of which are joined by an edge if and only if they have a common divisor greater than one i.e. they are not relatively prime. For an integer N, let kN be the least number such that a graph on kN1 vertices exists that is the P-graph of exactly one partition of N into kN parts. It has been shown, for example, that k200 6. Determining kN in general seems hopeless, but perhaps satisfactory estimates can be found. In particular, how big is, say, k1000 Less than 12, as estimated by this proposer Consider a cycle of length greater than 3. If we label the edges of this P-graph by the gcds, then a vertex on this cycle between two labels a and b must be a multiple of ab, and a and b are coprime. Thus all the labels are pairwise coprime and greater than 1, so the smallest k many such labels can be no smaller tha...
Комментарии
Отправить комментарий