A005488 Maximal number of edges in a b^{hat} graceful graph with n nodes. (Formerly M2528)

0, 1, 3, 6, 9, 13, 18, 24, 29

Offset

1,3

Comments

A graph with e edges is 'b^{hat} graceful' if its nodes can be labeled with distinct nonnegative integers so that, if each edge is labeled with the absolute difference between the labels of its endpoints, then the e edges have the distinct labels 1, 2, ..., e.

Equivalently, maximum m for which there's a difference basis with respect to m with n elements. A 'difference basis w.r.t. m' is a set of integers such that every integer from 1 to m is a difference between two elements of the set.

Miller's paper gives these lower bounds for the 11 terms from a(9) to a(19): 29,37,45,51,61,70,79,93,101,113,127. (Bermond's paper gives these as exact values, but quotes Miller as their source.)

References

J.-C. Bermond, Graceful graphs, radio antennae and French windmills, pp. 18-37 of R. J. Wilson, editor, Graph Theory and Combinatorics. Pitman, London, 1978.

R. K. Guy, Unsolved Problems in Number Theory, Sect. C10.

J. C. P. Miller, Difference bases: Three problems in additive number theory, pp. 299-322 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=1..9.

J. Leech, On the representation of 1, 2, ..., n by differences, J. Lond. Math. Soc. 31 (1956), 160-169.

Example

a(7)=18: Label the 7 nodes 0,6,9,10,17,22,24 and include all edges except those from 0 to 22, from 0 to 24 and from 17 to 24. {0,6,9,10,17,22,24} is a difference basis w.r.t. 18.

Crossrefs

Cf. A004137, A007187, A239308.

Sequence in context: A154287 A092847 A143975 * A048202 A014785 A132352

Adjacent sequences: A005485 A005486 A005487 * A005489 A005490 A005491

Keyword

nonn,more

Author

N. J. A. Sloane, Simon Plouffe

Extensions

Edited by Dean Hickerson, Jan 26 2003

a(9) from J. Stauduhar, May 04 2022

Status

approved