2
$\begingroup$

The vertices of any simple graph can be labeled in infinitely many ways with positive integers so that two vertices are joined by an edge if, and only if, they have a common divisor greater than 1.

Are there graphs for which there are infinitely many numbers that cannot be the sum of the labels in such a labeling of its vertices? Infinitely many? It has been shown, for example, that every sufficiently large number can be the sum of the labels in such a labeling of the Petersen graph (Finding the largest number which cannot be the sum of the labels of the Petersen graph).

$\endgroup$
6
$\begingroup$

A graph with 2 vertices works, any prime number can't be the sum of two numbers that have a common divisor greater than 1.

$\endgroup$
  • $\begingroup$ I think this answer should be accepted. $\endgroup$ – Gerardo Arizmendi Jun 12 '17 at 6:35

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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