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!)
A337278 Array read by antidiagonals: T(m,n) (m>=1, n>=1) is number of graceful labelings of the complete bipartite graph K_{m,n}. 3
1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 5, 1, 5, 1, 1, 2, 4, 4, 2, 1, 1, 4, 2, 4, 2, 4, 1, 1, 8, 4, 4, 4, 4, 8, 1, 1, 4, 3, 10, 1, 10, 3, 4, 1, 1, 3, 4, 5, 4, 4, 5, 4, 3, 1, 1, 14, 3, 11, 3, 7, 3, 11, 3, 14, 1, 1, 2, 5, 7, 4, 5, 5, 4, 7, 5, 2, 1, 1, 10, 2, 11, 3, 16, 2, 16, 3, 11, 2, 10, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,8

COMMENTS

A graceful labeling of a graph with q edges is an assignment of distinct numbers f(v) in {0,...,q} to the vertices in such a way that an edge between u and v is uniquely identified by |f(u)-f(v)|. In other words, for each j in {1,...,q} there's exactly one edge such that |f(u)-f(v)|=j.

We don't distinguish between a labeling and its complement with respect to q. (The complement is obtained by changing f(v) to q-f(v) for each v.)  We also don't distinguish between labelings that differ only because of automorphisms of the graph.

In the case of K_{m,n} we have, of course, q=mn edges. This graph has m!n! automorphisms when m<>n, and 2m!n! automorphisms when m=n. According to our conventions, K_{2,2} has only one graceful labeling, namely

  0,1 | 2,4

[meaning that the labels in one part are {0,1} and the labels in the other part are {2,4}]; but 16 different functions f actually satisfy the conditions: 8 because of the automorphisms, times 2 for complement. The complement of the labeling above is

  0,2 | 3,4

Here's another example: There are four graceful ways to label K_{3,4} namely

  0,1,2 | 3,6,9,12

  0,2,4 | 5,6,11,12

  0,3,7 | 1,10,11,12

  0,4,8 | 9,10,11,12

LINKS

Filip Stappers, Table of n, a(n) for n = 1..276

Joseph A. Gallian, Graph Labeling, Electron. J. Combin., Dynamic Survey 6.

Don Knuth, CWEB program to generate solutions

Filip Stappers, Extra terms up to m,n = 23

EXAMPLE

The array begins:

..1..1..1..1..1..1..1..1..1..1..1..1..1..1..1..1,...

..1..1..2..5..2..4..8..4..3.14..2.10.20..4..4.39,...

..1..2..1..4..2..4..3..4..3..5..2..6..3..4..4..6,...

..1..5..4..4..4.10..5.11..7.11..4.19..5.10.10.17,...

..1..2..2..4..1..4..3..4..3..5..2..6..3..4..4..6,...

..1..4..4.10..4..7..5.16..9.15..4.30..5.14.14.26,...

..1..8..3..5..3..5..2..5..4..6..3..7..4..5..5..7,...

..1..4..4.11..4.16..5.10.10.17..4.40..5.16.16.36,...

..1..3..3..7..3..9..4.10..3.10..3.18..4..9..9.16,...

..1.14..5.11..5.15..6.17.10..8..5.31..6.15.15.27,...

..1..2..2..4..2..4..3..4..3..5..1..6..3..4..4..6,...

..1.10..6.19..6.30..7.40.18.31..6.42..7.30.30.76,...

..1.20..3..5..3..5..4..5..4..6..3..7..2..5..5..7,...

..1..4..4.10..4.14..5.16..9.15..4.30..5..7.14.26,...

..1..4..4.10..4.14..5.16..9.15..4.30..5.14..7.26,...

..1.39..6.17..6.26..7.36.16.27..6.76..7.26.26.36,...

...

The first few antidiagonals are:

1,

1,1,

1,1,1,

1,2,2,1,

1,5,1,5,1,

1,2,4,4,2,1,

1,4,2,4,2,4,1,

1,8,4,4,4,4,8,1,

1,4,3,10,1,10,3,4,1,

...

CROSSREFS

Cf. A337279.

Sequence in context: A064552 A209543 A178655 * A178304 A123585 A145668

Adjacent sequences:  A337275 A337276 A337277 * A337279 A337280 A337281

KEYWORD

nonn,tabl

AUTHOR

N. J. A. Sloane, Sep 11 2020, based on a communication from Don Knuth, Sep 08 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 June 12 23:14 EDT 2021. Contains 344979 sequences. (Running on oeis4.)