Graceful graphs with Valence $k$

The graph complement of the following is a graceful graph of valence 11 with 99 edges and 18 vertices. There are likely millions of such graphs, but they are hard to find. This definitely isn't the prettiest of them. A valence 11 graph with 88 edges is provably impossible by brute force.

The graph complement of the following is a graceful graph of valence 13 with 130 edges and 20 vertices. There are likely millions of such graphs within the 14189192868003840 possibilities.

A graceful graph with minimal vertices usually has vertex values that make a sparse ruler. I've collected about 10^6 sparse rulers to length 1200. The following gives an upper bound to at least edges=1200.

Graceful Graph Conjecture: When a graceful graph with $e$ edges and $v$ vertices has the minimum possible vertices, then $v - \lceil \sqrt{3 \times e +9/4} \rfloor \in (0,1)$ and the vertex set is a sparse ruler.

Up to length 213 the value is zero except for edgecounts 51, 59, 69, ... ( A308766) where the value is one. For the lower bound I'll note that sparse rulers are heavily related to each other. Most sparse rulers can generate hundreds of other sparse rulers of larger and smaller sizes through simple operations. If a graceful graph / sparse ruler existed so that $v - \lceil \sqrt{3 \times e +9/4} \rfloor = -1$, it would likely generate ripples to larger and smaller values. No such ripples are seen up to length 213.

John Leech ("On the "Representation of 1,2,...,n by Differences", J. of London Math Soc, April 1956) gave bounds of $\sqrt{2.434 n}$ and $\sqrt{3.348 n}$. We can compare these bounds to best known actual values now that we have them. For values 51, 59, 69 his upper bound is too low.

Some sparse rulers can have one internal mark removed and only miss a single value. For example, $0, 1, 2, 3, 7, 13, 15, 24, 33, 42, 51, 60, 63, 67, 70$ can have the mark at 3 removed so that only a difference of 64 is missing. From all of the thousands of sparse rulers I have with excess 0, none of them with length>70 has this property. Do any more exist? Many with excess 1 have this property, such as $0, 1, 3, 8, 9, 10, 17, 24, 37, 50, 63, 76, 89, 102, 115, 128, 134, 140, 145, 146, 149, 150$ which can have the 149 removed and only miss a difference of 148.

If the valence is even, the graph is Eulerian. Rosa 1967 "On Certain Valuations of the Vertices of a Graph" proved that an Eulerian graceful graph must have edges (mod 4) $\in (0,3)$. Based on sparse ruler data and this mod requirement we can make a grid of potential graceful graphs with even valence. The first six of these are verified above.

For odd valences there isn't a modulus requirement. Here are some potential graceful graphs with odd valence. The first five of these are verified above.

It is possible that some of the sparse rulers with length>213 and excess 1 are improvable to have excess 0. If those sparse rulers exist, that opens up the following potential graceful graphs.

It's possible that the smallest graceful graph with valence $2 n$ will have $3 n^2$ edges.

If some of those excess values really are unimprovable here are some potential graphs not based on sparse rulers that can fill in missing valence values.

Based on my latest results behavior for valences 4-37 should be as follows: Vertices: {6, 8, 9, 10, 12, 14, 15, 18, 18, 20, 21, 24, 24, 26, 27, 30, 32, 32, 36, 36, 37, 38, 40, 42, 44, 44, 48, 48, 49, 50, 51, 54, 56, 56}
Edges: {12, 20, 27, 35, 48, 63, 75, 99, 108, 130, 147, 180, 192, 221, 243, 285, 320, 336, 396, 414, 444, 475, 520, 567, 616, 638, 720, 744, 784, 825, 867, 945, 1008, 1036}

A plot of edges/valence^2

Another foible in the problem is luck. Above I give the minimal possible graceful graphs with valences 2 to 10 and a minimal graph for valence 12. For valence 7 the graph is unique. There are only five sparse rulers of length 35 and each can only generate a few hundred graceful graphs. By the luck of the draw, exactly one of those 2688 graphs had valence 7.

The sparse ruler for length 88 is unique. None of the 53 million graceful graphs it generates is 11-regular. The number of edges needs to divisible by 11, so the solution will have 99 edges and 18 vertices.

The luck issue may evaporate for higher orders. For example, length 130 happens to have exactly 130 sparse rulers with 20 marks. They can produce 14189192868003840 graceful graphs. For length 147 there are only five sparse rulers, but chances are good that one of the 1775755607408640 graceful graphs they generate has valence 14.

I have a few programs for taking a sparse ruler / vertex set and finding a graph with certain properties, such as the non-regular graceful graph below. My programs need further speed-ups to tackle the higher valences.