A350011 Numbers which are the minimal "product-weight" of a simple connected graph over the sequence of primes. See comments for precise definition.

6, 16, 30, 31, 35, 45, 52, 57, 60, 66, 67, 74, 78, 101

Offset: 1

Author

Meir-Simchah Panzer, Dec 08 2021

Keywords

• nonn
• more

Comments

Label the nodes of a simple connected graph on N nodes with integers from a sequence s starting from s(1), then s(2), s(3), ..., s(N). Assign to each edge a value equal to the product of its nodes' labels. Sum the edge values of the graph. The possible values of a graph are its 'product-weight' over the sequence s. This sequence a(n) comprises the minimal product-weight of simple, connected graphs over the sequence of primes, listed in ascending order.

Among N-node graphs, the graph with the smallest minimal product-weight will be a star graph, and the graph with the largest minimal product-weight will be the complete graph. Minimal product-weights are partially ordered by number of edges (e.g., 5-node graphs with 4 edges have smaller product-weights than the complete graph over 4-nodes which has 6 edges); so there are values missing from the sequence above, which includes simple connected graphs for 2, 3, and 4 nodes, as well as 4 5-node graphs and the 6-node star graph; e.g., if the terms listed so far included minimal product-weights for simple connected graphs of 2, 3, and 4 nodes, it would have a maximum value 101 and it would have skipped the value of 78 which is the minimal product-weight of the 6-node start graph.

Can different graphs have the same minimal product-weight?

Examples

			Consider a graph of 4 nodes A, B, C, D, with edges AB, AC, AD, BC. The labeling which corresponds to the minimal product-weight labels A as 2, B as 3, C as 5, and D as 7, and its minimal product-weight is 45. (Its maximal product-weight is 85.)