A337965 - OEIS

A337965

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

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

(list; graph; refs; listen; history; text; internal format)

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.

LINKS

Table of n, a(n) for n=1..8.

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

Cf. A337274, A334613.