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

Author

Don Knuth, Dec 21 2020

Keywords

• nonn
• more

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

Examples

			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.
		

References

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

Links

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

Crossrefs

Cf. A333728.

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