A334613 -id:A334613 - cp's OEIS frontend

A342225 Total number of ordered graceful labelings of graphs with n edges.

1, 2, 4, 12, 40, 182, 906, 5404, 35494, 264178, 2124078, 18965372, 181080940, 1879988162, 20764521072, 246377199752, 3085635516364, 41182472709986, 577129788232678, 8552244962978250, 132591961730782524, 2161198867136837458

Offset: 1

Don Knuth, Mar 06 2021

Also the number of sequences l_0, l_1, ..., l_{n-1} such that 0 <= l_k <= k and such that l_j+n-j != l_k for 0 <= j,k < n.
Ordered graceful labelings were originally called "near alpha-labelings". They have also been called "gracious labelings" and "beta^+-labelings.
The corresponding number of "true" alpha-labelings is A005193(n).
The corresponding number of unrestricted graceful labelings is A000142(n).
The corresponding number of unrestricted graceful labelings of bipartite graphs is 2*A334613(n+1).
Hence A005193(n) <= a(n) <= 2*A334613(n+1) <= A000142(n).

			For n=4 the a(4)=12 solutions l_0l_1l_2l_3 are 0000, 0001, 0011, 0012, 0020, 0022, 0101, 0103, 0111, 0112, 0122, 0123. (Of these, 0022 and 0103 are not counted by A005193.)

D. E. Knuth, The Art of Computer Programming, Volume 4B, Section 7.2.2.3 will have an exercise based on this sequence.

S. I. El-Zanati, M. J. Kenig, and C. Vanden Eynden, Near α-labelings of bipartite graphs, Australasian Journal of Combinatorics, 21 (2000), 275-285.

Cf. A000142, A005193, A334613.

a(18)-a(22) from Bert Dobbelaere, Mar 09 2021

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

Original entry on oeis.org

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

Offset: 1

Don Knuth, Oct 05 2020

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.

			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.

Cf. A337274, A334613.

a(8) from Bert Dobbelaere, Sep 09 2022

cp's OEIS Frontend

A342225 Total number of ordered graceful labelings of graphs with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions