I am a total beginner in this field and i‘m not really versed in the terminology, so please bare with me.

What I know, is that a graceful labeling, refers to a tree with $n$ vertices, where each vertex is assigned a value that is smaller than the number of edges, and that are connected by an edge that has the value of the difference between the two vertices, and where all edges have a distinct value. (Did I miss something?)

Now, you can separate trees into different classes, like: path, cycle, web, wheel, helm, gear, rectangular, $n$-dimensional hypercube, caterpillar, and lobster (with perfect matching) graphs, which are all proven to be graceful. (Did I miss any?)

Are there any special classes/types of graphs that couldn't be proven until now?

And does the Ringel-Kotzig-Conjecture refer to any kind of tree (trees with loops and without, for example), or only to a specific class/classes?

  • $\begingroup$ Are you refering to youtube.com/watch?v=v5KWzOOhZrw&app=desktop ? $\endgroup$ – Roddy MacPhee Feb 21 at 14:09
  • $\begingroup$ That’s where i first heard about it :D but i don‘t think i‘m refering to the video per se^^ $\endgroup$ – Lexyth Feb 21 at 14:13
  • $\begingroup$ The show in the video that a cycle path alone can't work. $\endgroup$ – Roddy MacPhee Feb 21 at 14:21
  • $\begingroup$ Uhm... yes it can. If you do 0,1,3 then the differences will be 1,2,3, so it works. Btw, they don‘t say it in the video, but you can number the labels with <=n where n is the number of joints. So for 3 joints it’s 0-3 $\endgroup$ – Lexyth Feb 21 at 14:25
  • $\begingroup$ en.m.wikipedia.org/wiki/Tree_(graph_theory) cycles are no longer trees. $\endgroup$ – Roddy MacPhee Feb 21 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.