OFFSET
1,3
COMMENTS
Consider vertices numbered 0 thru 3n. Add the edges 0--3n, 1--3n, and either 0--(3n-k), 1--(3n-k+1), ... or k--(3n-k) for 2 <= k < 3n. (Altogether (3n-1)!/2 possibilities.) If the resulting graph has 2n vertices of degree 3, and n+1 isolated vertices, we have gracefully labeled a cubic graph of 2n vertices.
EXAMPLE
When n = 3 the five labelings are:
0-9, 1-9, 1-8, 2-8, 0-5, 1-5, 2-5, 0-2, 8-9;
0-9, 1-9, 1-8, 2-8, 0-5, 5-9, 2-5, 0-2, 1-2;
0-9, 1-9, 2-9, 0-6, 1-6, 1-5, 2-5, 0-2, 5-6;
0-9, 1-9, 2-9, 1-7, 2-7, 0-4, 4-7, 2-4, 0-1;
0-9, 1-9, 2-9, 0-6, 1-6, 2-6, 0-3, 1-3, 2-3.
The first four are graceful labelings of the prism K3 x K2. The fifth is a graceful labeling of the utilities graph K3,3.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Don Knuth, Oct 05 2020
EXTENSIONS
a(8) from Bert Dobbelaere, Sep 09 2022
STATUS
approved