A333728 -id:A333728 - cp's OEIS frontend

A334307 Number of graceful labelings for the complete tripartite graph K_{1,1,n}.

12, 32, 168, 1152, 9600, 97920, 1491840, 21127680, 377395200, 7605964800, 164457216000, 3935477145600, 102571486617600, 2858053098700800, 85725900868608000, 2745404797943808000, 93266934645620736000, 3356738924418367488000, 127589166595209166848000

Offset: 1

Eric W. Weisstein, Apr 24 2020

nonn

Except for n = 2, a(n) = A333728(n+2) up to at least n = 6.

Paolo Xausa, Table of n, a(n) for n = 1..400 (terms 1..48 from Don Knuth)
Eric Weisstein's World of Mathematics, Complete Tripartite Graph
Eric Weisstein's World of Mathematics, Graceful Labeling

Cf. A333728 (maximum number of graceful labelings for an n-node simple graph), A339891.

A334307[n_]:=If[n==1,12,4n!(DivisorSum[2n+1,2^((#-1)/2)&]+DivisorSigma[0,n+1]-2^(n-1)-1)];Array[A334307, 25] (* Paolo Xausa, Dec 04 2023 *)

If n>1, a(n) = 4*A339891(n)*n!. - Don Knuth, Dec 21 2020.

a(8) and a(9) from Pontus von Brömssen, Jul 25 2020

Terms a(10) and beyond from Don Knuth, Dec 21 2020

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

Original entry on oeis.org

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

Offset: 2

Don Knuth, Dec 21 2020

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

			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.

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

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

Cf. A333728.

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

cp's OEIS Frontend

A334307 Number of graceful labelings for the complete tripartite graph K_{1,1,n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions