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
    Commented Jun 12, 2017 at 6:35
  • $\begingroup$ Don´t you like my answer? Maybe you need an explanation? $\endgroup$
    – Gerardo Arizmendi
    Commented May 9, 2020 at 7:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .