

A005488


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


5




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.


REFERENCES

J.C. Bermond, Graceful graphs, radio antennae and French windmills, pp. 1837 of R. J. Wilson, editor, Graph Theory and Combinatorics. Pitman, London, 1978.
R. K. Guy, Unsolved Problems in Number Theory, Sect. C10.
J. Leech, On the representation of $1,2,\cdots,n$ by differences. J. London Math. Soc. 31 (1956), 160169.
J. C. P. Miller, Difference bases: Three problems in additive number theory, pp. 299322 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..8.


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


AUTHOR

N. J. A. Sloane, Simon Plouffe


EXTENSIONS

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, Jan 26 2003


STATUS

approved



