A337965 - OEIS

%I #22 Sep 09 2022 13:21:50

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

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

%C 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.

%e When n = 3 the five labelings are:

%e   0-9, 1-9, 1-8, 2-8, 0-5, 1-5, 2-5, 0-2, 8-9;

%e   0-9, 1-9, 1-8, 2-8, 0-5, 5-9, 2-5, 0-2, 1-2;

%e   0-9, 1-9, 2-9, 0-6, 1-6, 1-5, 2-5, 0-2, 5-6;

%e   0-9, 1-9, 2-9, 1-7, 2-7, 0-4, 4-7, 2-4, 0-1;

%e   0-9, 1-9, 2-9, 0-6, 1-6, 2-6, 0-3, 1-3, 2-3.

%e The first four are graceful labelings of the prism K3 x K2. The fifth is a graceful labeling of the utilities graph K3,3.

%Y Cf. A337274, A334613.

%K nonn,more

%O 1,3

%A _Don Knuth_, Oct 05 2020

%E a(8) from _Bert Dobbelaere_, Sep 09 2022