2
$\begingroup$

Do graceful graphs exist with more than any arbitrarily large number of vertices, all of which are labelled with a prime or non-negative square number.

Recall that a graceful graph is a graph with m edges whose vertices can be labelled with some subset of the integers between 0 and m inclusive, no two vertices sharing a label, and each of its edges uniquely identified by the absolute difference between its end points (so that this magnitude lies between 1 and m inclusive).

There is evidence (https://math.stackexchange.com/questions/3253495/integers-as-differences-of-squares-and-primes/3253666#3253666) that the answer to this is no, but a proof is lacking.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

This graceful graph has 151 vertices and 683 edges. All vertices are prime or square. No such graceful graph exists with more edges than this and fewer than 50000.

Graceful graph

This graphs shows the number of numbers between $1$ and $n$ that are left out.

enter image description here

Improve this answer
$\endgroup$

You must log in to answer this question.

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