|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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?
|
|
LINKS
|
|
|
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
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|