A339892 Maximum number of fundamentally different graceful labelings for a simple graph of n nodes without isolated vertices.

1, 1, 5, 26, 126, 680, 3778

Offset

2,3

Comments

The difference between "fundamentally different graceful labelings" of a graph and "graceful labelings" of a graph is that the latter is the former multiplied by twice the number of automorphisms. (The extra factor of 2 comes from complementation.)

a(9) >= 22033. - Eric W. Weisstein, Feb 07 2025

References

D. E. Knuth, The Art of Computer Programming, Section 7.2.2.3, in preparation.

Links

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

Eric Weisstein's World of Mathematics, Graceful Labeling.

Eric Weisstein's World of Mathematics, Maximally Graceful Graph.

Example

For n=4 the "paw" graph has a(4)=5 fundamentally different labelings, namely with edges
  0-4,0-3,0-2,2-3 or
  0-4,0-3,0-2,3-4 or
  0-4,0-3,1-3,0-1 or
  0-4,0-3,1-3,3-4 or
  0-4,0-3,2-4,3-4.
The other six graphs with four vertices are either ungraceful (2K_1) or uniquely graceful (K_1,3, K_4, C_4, P_4) or have fewer than 5 (K_1,1,2 has 4).
For n=5 the "dart" has a(5)=26 fundamentally different labelings.

Crossrefs

Cf. A333728.

Cf. A379395 (maximum number of fundamentally different graceful labelings allowing graphs with isolated vertices).

Sequence in context: A285905 A344218 A247491 * A379395 A244617 A003583

Adjacent sequences: A339889 A339890 A339891 * A339893 A339894 A339895

Keyword

nonn,more

Author

Don Knuth, Dec 21 2020

Status

approved