1,3

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.

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.

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

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.

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

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.

Cf. A004137, A007187.

Sequence in context: A076523 A129403 A092847 this_sequence A048202 A014785 A132352

Adjacent sequences: A005485 A005486 A005487 this_sequence A005489 A005490 A005491

nonn

njas, Simon Plouffe (plouffe(AT)math.uqam.ca)

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.)

Edited by Dean Hickerson (dean(AT)math.ucdavis.edu), Jan 26 2003