16
$\begingroup$

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?

Petersen graph

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?

$\endgroup$
7
  • 1
    $\begingroup$ I would take two disjoint edge matchings and label one matching with the 5 largest primes, then the second with the next largest, and then tweak the remaining edges to minimize the sum using the 5 smallest primes. I think one can get something near 40000 this way. Gerhard "Has Not Tried It Himself" Paseman, 2017.05.18. $\endgroup$ May 19, 2017 at 3:53
  • 1
    $\begingroup$ @GerhardPaseman The Petersen graph doesn't have two disjoint matchings; maybe you meant something else? $\endgroup$ May 19, 2017 at 4:50
  • $\begingroup$ Indeed. Then I guess brute force it is. There may be an edge swapping algorithm which will give a local minimum. Gerhard "Maybe Choose Nine Edges Optimally?" Paseman, 2017.05.18. $\endgroup$ May 19, 2017 at 4:55
  • 5
    $\begingroup$ Notice that you are looking for a labeling of the edges by the 15 smallest primes. The Petersen graph has symmetry group $S_5$ so that means that there are, in principle, $15!/5!$ possibilities to check, which is probably still too much to check one by one by computer. $\endgroup$ May 19, 2017 at 7:57
  • 1
    $\begingroup$ There are three disjoint configurations of five edges, which means 6 of the ten vertices form three pairs that are "sort of" independent. If the sum of the six vertices exceeds the known minimum with that partition, one can eliminate all permutations associated with that partition. Still brute force, but probably this involves checking only 10 million cases or so. Gerhard "Combinatorial Optimization Is My Game" Paseman, 2017.05.19. $\endgroup$ May 19, 2017 at 14:58

4 Answers 4

15
$\begingroup$

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.

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ You are the winner! $\endgroup$ May 22, 2017 at 23:16
11
$\begingroup$

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.)

$\endgroup$
10
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ If you pick 4 primes for the edges surrounding 47, many of them will fail to achieve your minimum just summing for the two vertices. Many more will fail when you take one or two more vertices into consideration. I suspect you will find a feasible number of edge labelings surrounding the edge labelled 47 that might have a chance of beating your bound. Gerhard "Global Minimum Is Within Reach" Paseman, 2017.05.20. $\endgroup$ May 20, 2017 at 8:05
9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Given that there is a solution with sum under 40000, a breadth first search should also be feasible. Pick an edge labeled 47, form the set V of unordered pairs of primes which has 91 members, and start adding members of V to keep under the constraint. If you always add a V to the largest edge, you will prune the tree quickly. You will be left with (I suspect) much fewer than a million labellings with less than 50 ways to finish each labelling. Gerhard "V Means Two Adjacent Edges" Paseman, 2017.05.22. $\endgroup$ May 22, 2017 at 16:06
  • $\begingroup$ Thanks to Gordon Royle (see below) for confirming this optimum. $\endgroup$ May 23, 2017 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.