Wolfram Research

GracefulGraphFromPermutation

Contributed by: Ed Pegg Jr

Source Notebook

Show the graceful graph corresponding to a given permutation

ResourceFunction["GracefulGraphFromPermutation"][perm]

For the permutation perm show the graceful graph.

Details and Options

A graceful graph has n edges labeled 1 to n, with each edge label equal to the absolute difference between the labels of its vertices.

Examples

Basic Examples

Every permutation can be converted to a graceful graph:

In[1]:=
ResourceFunction[
 "GracefulGraphFromPermutation"][{1, 2, 9, 5, 4, 12, 7, 6, 3, 11, 10, 8}]
Out[1]=

Scope

Some graceful graphs are planar:

In[2]:=
ResourceFunction[
 "GracefulGraphFromPermutation"][{2, 3, 6, 5, 8, 1, 7, 4}]
Out[2]=

Any random permutation can give a graceful graph:

In[3]:=
ResourceFunction["GracefulGraphFromPermutation"][
 RandomSample[Range[18]]]
Out[3]=

Some graceful graphs are trees:

In[4]:=
ResourceFunction[
 "GracefulGraphFromPermutation"][{2, 7, 10, 4, 6, 9, 8, 3, 1, 5}]
Out[4]=

Resource History