A labelling of the vertices of the Petersen graph with integers

Question

The vertices of the Petersen graph (or any other simple graph) can be labelled in infinitely many ways with positive integers so that two vertices are joined by an edge if, and only if, the corresponding labels have a common divisor greater than 1. (One such labelling is with the numbers 645, 658, 902, 1085, 1221, 13243, 13949, 14053, 16813, and 17081, whose sum is 79650). Of all such ways of labelling the Petersen graph, what is the minimum the sum of the 10 corresponding integers can be?

The reason to single out the Petersen graph over all other graphs of order ten or less is that it is one particularly difficult to label if one is trying to achieve the minimum sum. Is there some systematic why of finding that minimum other than brute force?

Answer 1

The following labelling, whose sum is $37294$, improves Aaron Meyerowitz's by $64$. It was also found by extensive computer search, but with the strategy of assigning and fixing the first five primes (in all possible permutations) to the edges joining the vertices of the exterior and interior pentagons, and then examining the resulting sums of assigning all $10!$ possible permutations of the next ten primes to the remaining $10$ edges.

This by no means exhausts all possibilities, but does seem to come close to the optimal solution.

The above figure shows the initial assignment of the first five primes to the vertices of the graph.

Answer 2

The minimum value is $37294$ as described by F. Barrera.

I broke the symmetry a little by identifying $9$ inequivalent triples of edges to which the primes $\{41,43,47\}$ can be assigned, wrote a constraint satisfaction program for the problem, and then used Minion to solve it.

(I am sure there are more efficient ways to do this.)

Answer 3

With some computer searching I can get a sum of $37358$ and another of $37360.$ I list them below. I'm not saying they are optimal, though they seem pretty good.

The ten vertex labels should multiply to $N^2$ where $N$ is the product of the first $15$ primes. If they were allowed to be positive reals subject to this product then the minimum sum would come from setting them all to $N^{1/5} \approx 3612.1.$ Hence 36121 is a lower bound for the minimum possible sum.

The two examples are

$ [4879, 3913, 3182, 2162, 3995, 3441, 2337, 4807, 4147, 4495]=$ $ [ 7\cdot17\cdot41, 7\cdot13\cdot43, 2\cdot37\cdot43, 2\cdot23\cdot47, 5\cdot17\cdot47, $ $ 3\cdot31\cdot37, 3\cdot19\cdot41,11\cdot19\cdot23,11\cdot13\cdot29,5\cdot29\cdot31] $

with sum $37358$

And $[2337, 2726, 3055, 3182, 3565, 3731, 3999, 4301, 4403, 6061]=$ $[ 3\cdot 19\cdot 41 , 2\cdot 29\cdot 47 , 5\cdot 13\cdot 47 , 2\cdot 37\cdot 43 , 5\cdot 23\cdot 31 ,$ $ 7\cdot 13\cdot 41 , 3\cdot 31\cdot 43 , 11\cdot 17\cdot 23 , 7\cdot 17\cdot 37 , 11 \cdot 19\cdot 29 ] $

with sum $37360.$

These are each minimal under switching any two edge labels. checking all $2\binom{15}{3}$ cyclic three way switches before or after didn't improve anything.

The next smallest sums from $2000000$ random labellings followed by optimization were $37438, 37458, 37490, 37494$

Answer 4

It is possible to exploit the symmetries of the Petersen graph, together with the rearrangement inequality, to reduce the size of a brute-force search from $15!$ to $129729600$ (a $10080$-fold improvement).

• Draw the Petersen graph in the usual way, with an outer pentagon (consisting of red edges), an inner pentagram (blue edges), and five green spokes connecting them.

• Fix one of the red edges to have the label $2$ (we can do this since the Petersen graph is edge-transitive).

• There is an automorphism fixing the edge labelled $2$ and sending any other specified edge to a green edge. Consequently, we shall assume that $3$ is one of the green edges.

• By a further symmetry (namely the element of $D_{10}$ which fixes the edge labelled $2$), we may assume that the red edge to the anticlockwise of $2$ is greater than the red edge to the clockwise of $2$.

Now, choose four remaining primes and label the remaining red edges (there are $\frac{1}{2}(13 \times 12 \times 11 \times 10) = 8580$ ways to do so), where the factor of $\frac{1}{2}$ is due to the point mentioned above.

Choose five remaining primes and label the blue edges (there are $9 \times 8 \times 7 \times 6 \times 5 = 15120$ ways to do so).

The five remaining primes, $p_1, p_2, p_3, p_4, p_5$, will label the green spokes. Instead of checking all $5! = 120$ permutations, we can appeal to the rearrangement inequality. Specifically, temporarily label each vertex with the product of the two existing primes incident with it. For each green edge $e_i$, let $q_i$ be the sum of the labels of the two endpoints. Now, we wish to minimise the sum of products:

$$ p_1 q_{\sigma(1)} + p_2 q_{\sigma(2)} + p_3 q_{\sigma(3)} + p_4 q_{\sigma(4)} + p_5 q_{\sigma(5)} $$

by choosing some permutation $\sigma \in S_5$. But the rearrangement inequality tells us that the best way to do so is to order the $p_i$ in ascending order, and the $q_i$ in descending order; the resulting sum of products is minimal.

---

Suddenly a brute-force search is starting to look very feasible: $129729600$ iterations should not take very long at all, even when each iteration requires sorting a list of five integers. The fact that it breaks down into $8580$ smaller searches makes this amenable to parallelisation.