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.

$\endgroup$
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

| cite | improve this answer | |
$\endgroup$

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.