login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A339892 Maximum number of fundamentally different graceful labelings for a simple graph of n nodes without isolated vertices. 1
1, 1, 5, 26, 126, 680, 3778 (list; graph; refs; listen; history; text; internal format)
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.)

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

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.

Sequence in context: A285905 A344218 A247491 * A244617 A003583 A033115

Adjacent sequences:  A339889 A339890 A339891 * A339893 A339894 A339895

KEYWORD

nonn,more

AUTHOR

Don Knuth, Dec 21 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 17 12:55 EDT 2021. Contains 343971 sequences. (Running on oeis4.)