A337965 Total number of graceful labelings of cubic graphs with 2n vertices.

0, 1, 5, 222, 22806, 2988280, 641731574, 204154267353

Offset: 1

Author

Don Knuth, Oct 05 2020

Keywords

• nonn
• more

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.

Examples

			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

Cf. A337274, A334613.

Extensions

a(8) from Bert Dobbelaere, Sep 09 2022