cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A033472 Number of n-vertex labeled graphs that are gracefully labeled trees.

Original entry on oeis.org

1, 1, 2, 4, 12, 40, 164, 752, 4020, 23576, 155632, 1112032, 8733628, 73547332, 670789524, 6502948232, 67540932632, 740949762580, 8634364751264, 105722215202120, 1366258578159064, 18468456090865364, 262118487952306820
Offset: 1

Views

Author

Glenn G. Chappell

Keywords

Comments

A graph with n edges is graceful if its vertices can be labeled with distinct integers in the range 0,1,...,n in such a way that when the edges are labeled with the absolute differences between the labels of their end-vertices, the n edges have the distinct labels 1,2,...,n.
The PARI/GP program below uses the Matrix-Tree Theorem and sums over {1,-1} vectors to isolate the multilinear term. It takes time 2^n * n^O(1) to compute graceful_tree_count(n). - Noam D. Elkies, Nov 18 2002
Noam D. Elkies and I have independently verified the existing terms and computed more, up to a(31). - Don Knuth, Feb 09 2021

Examples

			For n=3 we have 1-3-2 and 2-1-3, so a(3)=2.

References

  • A. Kotzig, Recent results and open problems in graceful graphs, Congressus Numerantium, 44 (1984), 197-219 (esp. 200, 204).

Links

Crossrefs

Cf. A006967, A337274.

Programs

  • PARI
    { treedet(v, n) = n=length(v); matdet(matrix(n,n,i,j, if(i-j,-v[abs(i-j)], sum(m=1,n+1,if(i-m,v[abs(i-m)],0))))) }
{ graceful_tree_count(n, s,v,v1,v0)= if(n==1,1, s=0; v1=vector(n-1,m,1); v0=vector(n-1,m,if(m==1,1,0)); for(m=2^(n-2),2^(n-1)-1, v= binary(m) - v0; s = s + (-1)^(v*v1~) * treedet(v1-2*v) ); s/2^(n-2) ) } \\ Noam D. Elkies, Nov 18 2002
for(n=1,18,print1(graceful_tree_count(n),", ")) \\ Example of function call

Formula

a(n) = 2 * A337274(n) for n >= 3. - Hugo Pfoertner, Oct 05 2020

A334613 Number of distinct graceful labelings of bipartite graphs with n vertices and n-1 edges.

Original entry on oeis.org

1, 1, 1, 2, 7, 28, 151, 907, 6467, 51151, 458478, 4455476, 48162974, 557022350, 7020022164, 94129389215, 1357181821028, 20661645476348
Offset: 1

Views

Author

Don Knuth, Sep 08 2020

Keywords

Comments

Consider vertices numbered 1 to n. Add the edges 1--n, 2--n, and either 1--(n+1-k), 2--(n+2-k), ... or k--n for 3<=k

Examples

			For example, the seven labelings for n=5 are:
  1--5, 2--5, 1--3, 2--3;
  1--5, 2--5, 1--3, 3--4;
  1--5, 2--5, 1--3, 4--5;
  1--5, 2--5, 2--4, 2--3;
  1--5, 2--5, 2--4, 3--4;
  1--5, 2--5, 3--5, 3--4;
  1--5, 2--5, 3--5, 4--5.
The first of these is the four-cycle plus an isolated vertex; the other six are the trees in A337274.

Crossrefs

Cf. A337274.

Extensions

a(17)-a(18) from Bert Dobbelaere, Sep 11 2020

A337965 Total number of graceful labelings of cubic graphs with 2n vertices.

Original entry on oeis.org

0, 1, 5, 222, 22806, 2988280, 641731574, 204154267353
Offset: 1

Views

Author

Don Knuth, Oct 05 2020

Keywords

Comments

Consider vertices numbered 0 thru 3n. Add the edges 0--3n, 1--3n, and either 0--(3n-k), 1--(3n-k+1), ... or k--(3n-k) for 2 <= k < 3n. (Altogether (3n-1)!/2 possibilities.) If the resulting graph has 2n vertices of degree 3, and n+1 isolated vertices, we have gracefully labeled a cubic graph of 2n vertices.

Examples

			When n = 3 the five labelings are:
  0-9, 1-9, 1-8, 2-8, 0-5, 1-5, 2-5, 0-2, 8-9;
  0-9, 1-9, 1-8, 2-8, 0-5, 5-9, 2-5, 0-2, 1-2;
  0-9, 1-9, 2-9, 0-6, 1-6, 1-5, 2-5, 0-2, 5-6;
  0-9, 1-9, 2-9, 1-7, 2-7, 0-4, 4-7, 2-4, 0-1;
  0-9, 1-9, 2-9, 0-6, 1-6, 2-6, 0-3, 1-3, 2-3.
The first four are graceful labelings of the prism K3 x K2. The fifth is a graceful labeling of the utilities graph K3,3.

Crossrefs

Cf. A337274, A334613.

Extensions

a(8) from Bert Dobbelaere, Sep 09 2022
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.