Back

@jsiehler Any idea whether you can label the Dyck graph (https://en.wikipedia.org/wiki/Dyck_graph) in the same way? Or is it just this graph?

@11011110 I know three 32-vertex graphs where you can do this and they are all vertex-transitive. The Dyck graph is one of them.

@jsiehler @11011110 Does this kind of graph labeling have a name or related literature?

@axiom I call them "xor-magic" graphs. I wrote up what little I know about them in an article that's currently under consideration. If you want to see where the idea first came up, search for the article "Slide-and-swap Permutation Groups"

@jsiehler @axiom If it has a name or prior publications I don't know about it. But it reminds me of several other more well-studied concepts:

* partial cubes (label vertices by bitstrings, not necessarily using all strings, so that Hamming distance = graph distance)

* graceful graphs (label vertices by numbers so that the differences of labels on the endpoints of each edge are the numbers from 1 to #edges)

* Tutte embedding, each vertex is centroid of neighbors https://en.wikipedia.org/wiki/Tutte_embedding