login
A350011
Numbers which are the minimal "product-weight" of a simple connected graph over the sequence of primes. See comments for precise definition.
0
6, 16, 30, 31, 35, 45, 52, 57, 60, 66, 67, 74, 78, 101
OFFSET
1,1
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?
EXAMPLE
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.)
CROSSREFS
Sequence in context: A032422 A164052 A264938 * A168472 A054000 A113742
KEYWORD
nonn,more
AUTHOR
Meir-Simchah Panzer, Dec 08 2021
STATUS
approved