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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think this answer should be accepted. $\endgroup$
    – Gerardo Arizmendi
    Jun 12, 2017 at 6:35
  • $\begingroup$ Don´t you like my answer? Maybe you need an explanation? $\endgroup$
    – Gerardo Arizmendi
    May 9, 2020 at 7:05

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.