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

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

Offset: 1

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• nonn
• more

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

Examples

			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.
		

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

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

Crossrefs

Cf. A004137, A007187, A239308.

Extensions

Edited by Dean Hickerson, Jan 26 2003

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