Does an Eulerian semi-graceful polyhedral graph exist? In a graceful graph, the vertices have number values that range from 0 to $n$ and $n$ edges with all values from 1 to $n$ that are differences between the vertex values. Here's a graceful but boring path graph with an Eulerian tour.

A more interesting graph is the Petersen graph, which can be labeled gracefully.

In this graph, 1-2-3 is a path for vertices 2-3-5-8. Three edges out of 15 means this is a 20% path.  An Eulerian path would be 100%.  Is there a graceful Eulerian labelling for anything other than the path graph? For a partial queen graph on a 4x4 grid, here is a semi-graceful labeling with length 36. 

Here is a similar semi-graceful graph. If vertices had values ranging from 0 and 29, then it would be a graceful graph. Let's call this an Eulerian semi-graceful graph.

For semi-graceful Eulerian graphs, are any of them interesting graphs? The vertex sequence 9, 10, 8, 5, 9, 14, 8, 1, 9, 0, 10, 21, 9, 22, 36, 21, 5, 22, 40, 21, 1, 22, 0, 23, 47, 22, 48, 21, 49, 78, 48, 79, 47, 14, 48, 83, 47, 10, 48, 9, 49, 90, 48, 5, 49, 94, 48, 1, 49, 0 can be used to make a 20 vertex graph with path length 49, but it isn't all that interesting. Is it possible to find a polyhedral graph with an Eulerian semi-graceful labeling?
For $n$ vertices, what is the longest possible path?
EDIT: Leen Droogendijk points out an Eulerian graceful graph. Are there others?

EDIT 2:  Turns out there are many Eulerian graceful graphs. So far, all of them seem to have at least one vertex with valence 1 or 2.

 A: First we show that there is no Eulerian graceful polyhedral graph.
Suppose a polyhedral graph can be created. For a polyhedral graph we need minimum degree 3. Since each vertex except the endpoints is even this means that for $n$ vertices we will need at least $2n-1$ edges. Even in the best case the last edge must go from $2n-1$ to 0, but this forces the edge of length $2n-2$ to vertex 1 etc.
In fact this forces so many vertices that you end up with more than $n$ forced vertices. Contradiction.
As an example: consider the case $n=5$. Walking backwards from the highest edge
we see that it must visit vertices $0,9,1,8,2,7,3$ (or an analogous sequence if we start with $9,0$). This is the first time we actually have a choice: the next edge can go to $0$ or to $6$, but we already visited 8 vertices. Clearly the situation gets even worse if our vertices have a higher degree.
The same argument confirms Ed's observation that there must always be a vertex of degree at most 2.
Answer to one of the other questions:
"Is there a graceful Eulerian labelling for anything other than the path graph?"
Yes, there is. Use vertices with labels $0,1,2,5,6$ and use the path $1,0,2,5,1,6,0$ (the path implies the edges). Since vertices 1 and 0 are used twice, this is not a path graph.
An "algorithm" to produce lots of them could be the following ("just focus on the edges, do not care about vertex labels").


*

*Start with an arbitrary long path using increasing edge labels $1,\ldots,n$.
You start with vertex label 0 and at each step decide arbitrarily whether you add or subtract the edge label to obtain the next vertex label.

*Add an arbitrary positive constant that is large enough to make all your vertex labels non-negative.

*Add a "positive path" (always adding your current edge label to the last vertex label) until your vertex label is at least half of the maximum value of your vertex labels until here.

*Zigzag back to zero, i.e. alternate adding and subtracting the next edge label. Because you started at at least half of the maximum value this guarantees that your last edge will be from the highest value to zero.

*Stop, or go back to step 3.
An almost complete argument that no polyhedral graph can be created: for a polyhedral graph we need minimum degree 3. Since each vertex except the endpoints is even this means that for $n$ vertices we will need at least $2n-1$ edges. Even in the best case the last edge must go from $2n-1$ to 0, but this forces the edge of length $2n-2$ to vertex 1 etc.
In fact this forces so many vertices that you end up with more than $n$ vertices. Contradiction.
