%I #37 Feb 07 2025 19:35:53

%S 1,1,5,26,126,680,3778

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

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

%C a(9) >= 22033. - _Eric W. Weisstein_, Feb 07 2025

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

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GracefulLabeling.html">Graceful Labeling</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MaximallyGracefulGraph.html">Maximally Graceful Graph</a>.

%e For n=4 the "paw" graph has a(4)=5 fundamentally different labelings, namely with edges

%e 0-4,0-3,0-2,2-3 or

%e 0-4,0-3,0-2,3-4 or

%e 0-4,0-3,1-3,0-1 or

%e 0-4,0-3,1-3,3-4 or

%e 0-4,0-3,2-4,3-4.

%e 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).

%e For n=5 the "dart" has a(5)=26 fundamentally different labelings.

%Y Cf. A333728.

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

%K nonn,more,changed

%O 2,3

%A _Don Knuth_, Dec 21 2020