A005488 -id:A005488 - cp's OEIS frontend

A004137 Maximal number of edges in a graceful graph on n nodes.

0, 1, 3, 6, 9, 13, 17, 23, 29, 36, 43, 50, 58, 68, 79, 90, 101, 112, 123, 138, 153, 168, 183, 198, 213, 232

Offset: 1

A graph with e edges is "graceful" if its nodes can be labeled with distinct integers in {0,1,...,e} 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 restricted 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. A "restricted" difference basis is one in which the smallest element is 0 and the largest is m.
a(n) is also the length of an optimal ruler with n marks. For definitions see A103294. For example, a(6)=13 is the length of the optimal rulers with 6 marks, {[0, 1, 6, 9, 11, 13], [0, 2, 4, 7, 12, 13], [0, 1, 4, 5, 11, 13], [0, 2, 8, 9, 12, 13], [0, 1, 2, 6, 10, 13], [0, 3, 7, 11, 12, 13]}. Also n = 1 + A103298(a(n)). - Peter Luschny, Feb 28 2005
If the conjecture is true that an optimal ruler with more than 12 segments is a Wichmann ruler then the sequence continues 232, 251, 270, 289, 308, 327, ... - Peter Luschny, Oct 09 2011 [updated to take the verifications of Robison into account, Oct 01 2015]

			a(7)=17: Label the 7 nodes 0,1,8,11,13,15,17 and include all edges except those from 8 to 15, from 13 to 15, from 13 to 17 and from 15 to 17. {0,1,8,11,13,15,17} is a restricted difference basis w.r.t. 17.
a(21)=153 because there exists a complete ruler (i.e., one that can measure every distance between 1 and 153) with marks [0,1,2,3,7,14,21,28,43,58,73,88,103,118,126,134,142,150,151,152,153] and no complete ruler of greater length with the same number of marks can be found. This ruler is of the type described by B. Wichmann and it is conjectured by _Peter Luschny_ that it is impossible to improve upon Wichmann's construction for finding optimal rulers of bigger lengths.

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, Modular difference sets and error correcting codes. in: Unsolved Problems in Number Theory, 3rd ed. New York: Springer-Verlag, chapter C10, (2004), 181-183.
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).

D. Beutner and H. Harborth, Graceful labelings of Nearly Complete Graphs, Results Math. 41 (2002) 34-39.
G. S. Bloom and S. W. Golomb, Applications of numbered undirected graphs, Proc. IEEE 65 (1977), 562-570.
G. S. Bloom and S. W. Golomb, Numbered complete graphs, unusual rulers, and assorted applications, Theory and Applications of Graphs, Lecture Notes in Math. 642, (1978), 53-65.
L. Egidi and G. Manzini, Spaced seeds design using perfect rulers, Tech. Rep. CS Department Universita del Piemonte Orientale, June 2011.
P. Erdős, A survey of problems in combinatorial number theory, Ann. Discrete Math. 6 (1980), 89-115.
P. Erdős and R. Freud, On sums of a Sidon-sequence, J. Number Theory 38 (1991), 196-205.
P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. Lond. Math. Soc. 16 (1941), 212-215.
J. Leech, On the representation of 1, 2, ..., n by differences, J. Lond. Math. Soc. 31 (1956), 160-169.
S. Lou and Q. Yao, A Chebyshev's type of prime number theorem in a short interval II, Hardy-Ramanujan J. 15 (1992), 1-33.
Peter Luschny, Perfect Rulers.
Peter Luschny, Wichmann Rulers.
Klaus Nagel, Evaluation of perfect rulers C program.
O. Pikhurko, Dense edge-magic graphs and thin additive bases, Discrete Math. 306 (2006), 2097-2107.
O. Pikhurko and T. Schoen, Integer Sets Having the Maximum Number of Distinct Differences, Integers: Electronic journal of combinatorial number theory 7 (2007).
I. Redéi and A. Rényi, On the representation of integers 1, 2, ..., n by differences, Mat. Sbornik 24 (1949), 385-389 (Russian).
Arch D. Robison, Parallel Computation of Sparse Rulers, Jan 14 2014.
F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, MRLA search results and source code, Nov 6 2020.
F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, Large Minimum Redundancy Linear Arrays: Systematic Search of Perfect and Optimal Rulers Exploiting Parallel Processing, IEEE Open Journal of Antennas and Propagation, 2 (2021), 79-85.
J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938), 377-85.
David Singmaster, David Fielker, N. J. A. Sloane, Correspondence, August 1979.
M. Wald & N. J. A. Sloane, Correspondence and Attachment, 1987.
Eric Weisstein's World of Mathematics, Graceful Graph.
B. Wichmann, A note on restricted difference bases, J. Lond. Math. Soc. 38 (1963), 465-466.
Al Zimmermann's Programming Contests, Graceful Graphs, September - December 2013.

Cf. A046693, A103294, A103298, A103299, A103296, A102508, A212661.
A080060 is an erroneous version of the sequence, given in Bermond's paper. Cf. A005488.
A289761 provides the conjectured continuation.

See Klaus Nagel link.
(Parallel C++) See A. Robison link.

a(n) = n*(n-1)/2 - A212661(n). - Kellen Myers, Jun 06 2016

Miller's paper gives these lower bounds for the 8 terms from a(15) to a(22): 79, 90, 101, 112, 123, 138, 153, 168.
Edited by Dean Hickerson, Jan 26 2003
Terms 79,...,123 from Peter Luschny, Feb 28 2005, with verification by an independent program written by Klaus Nagel. Using this program Hugo Pfoertner found the next term, 138.
Using this program Hugo Pfoertner found further evidence for the conjectured term a(21)=153, Feb 23 2005
Terms a(21) .. a(24) proved by exhaustive search by Arch D. Robison, Hugo Pfoertner, Nov 01 2013
Term a(25) proved by exhaustive search by Arch D. Robison, Peter Luschny, Jan 14 2014
Term a(26) proved by exhaustive search by Fabian Schwartau, Yannic Schröder, Lars Wolf, Joerg Schoebel, Feb 22 2021

A241094 Triangle read by rows: T(n,i) = number of gracefully labeled graphs with n edges that do not use the label i, 1 <= i <= n-1, n > 1.

Original entry on oeis.org

0, 1, 1, 4, 4, 4, 18, 24, 24, 18, 96, 144, 144, 96, 600, 960, 1080, 1080, 960, 600, 4320, 7200, 8460, 8460, 8460, 7200, 4320, 35280, 60840, 75600, 80640, 80640, 75600, 60480, 35280, 322560, 564480, 725760, 806400, 806400, 806400, 725760, 564480, 322560

Offset: 2

Christian Barrientos and Sarah Minion, Apr 15 2014

A graph with n edges is graceful if its vertices can be labeled with distinct integers in the range 0,1,...,n in such a way that when the edges are labeled with the absolute differences between the labels of their end-vertices, the n edges have the distinct labels 1,2,...,n.

			For n=7 and i=3, g(7,3) = 1080.
For n=7 and i=5, g(7,5) = 960.
Triangle begins:
[n\i]  [1]     [2]     [3]     [4]     [5]     [6]     [7]     [8]
[2]     0;
[3]     1,      1;
[4]     4,      4,      4;
[5]    18,     24,     24,     18;
[6]    96,    144,    144,    144,     96;
[7]   600,    960,   1080,   1080,    960,    600;
[8]  4320,   7200,   8640,   8640,   8640,   7200,   4320;
[9] 35280,  60480,  75600,  80640,  80640,  75600,  60480,  35280;
...
- _Bruno Berselli_, Apr 23 2014

C. Barrientos and S. M. Minion, Enumerating families of labeled graphs, J. Integer Seq., 18(2015), article 15.1.7.
J. A. Gallian, A dynamic survey of graph labeling, Elec. J. Combin., (2013), #DS6.
David A. Sheppard, The factorial representation of major balanced labelled graphs, Discrete Math., 15(1976), no. 4, 379-388.

Cf. A001563, A003022, A004137, A005488, A006967, A033472, A081621, A103300, A117747, A212661.

/* As triangle: */ [[i le Floor(n/2) select Factorial(n-2)*(n-1-i)*i else Factorial(n-2)*(n-i)*(i-1): i in [1..n-1]]: n in [2..10]]; // Bruno Berselli, Apr 23 2014

Labeled:=(i,n) piecewise(n<2 or i<1, -infinity, 1 <= i <= floor(n/2), GAMMA(n-1)*(n-1-i)*i, ceil((n+1)/2) <= i <= n-1, GAMMA(n-1)*(n-i)*(i-1), infinity):

n=10; (* This number must be replaced every time in order to produce the different entries of the sequence *)
For[i = 1, i <= Floor[n/2], i++, g[n_,i_]:=(n-2)!*(n-1-i)*i; Print["g(",n,",",i,")=", g[n,i]]]
For[i = Ceiling[(n+1)/2], i <= (n-1), i++, g[n_,i_]:=(n-2)!*(n-i)*(i-1); Print["g(",n,",",i,")=",g[n,i]]]

For n >=2, if 1 <= i <= floor(n/2), g(n,i) = (n-2)!*(n-1-i)*i; if ceiling((n+1)/2) <= i <= n-1, g(n,i) = (n-2)!*(n-i)*(i-1).
# alternative
A241094 := proc(n,i)
    if n <2 or i<1 or i >= n then
        0;
    elif i <= floor(n/2) then
        GAMMA(n-1)*(n-1-i)*i;
    else
        GAMMA(n-1)*(n-i)*(i-1) ;
    fi ;
end proc:
seq(seq(A241094(n,i),i=1..n-1),n=2..12); # R. J. Mathar, Jul 30 2024

Verified by brute-force search.
If A005488(9)=29, a(9)=690241543.
If A005488(10)=37, a(10)=18590862013118808193.
If A005488(11)=45, a(11)=2475880088154706432018350081.
If A005488(12)=51, a(12)=11331575459480141.

a(11) >= 48, a(12) >= 55.

a(n) is the greatest number k such that there exists a tree with n nodes and integral edge labels such that for each integer 1 <= m <= k, there exists a pair of nodes such that the sum of the edge labels on the path connecting the two nodes equals m. - Charlie Neder, Apr 26 2019

cp's OEIS Frontend

A335968 Smallest number whose binary representation has exactly n 1 bits and for which the differences of pairs of positions of the 1 bits include all positive integers up to and including A005488(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A004137 Maximal number of edges in a graceful graph on n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Formula

Extensions

A241094 Triangle read by rows: T(n,i) = number of gracefully labeled graphs with n edges that do not use the label i, 1 <= i <= n-1, n > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A007187 Leech's tree-labeling problem for n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A239308 Size of smallest set S of integers such that {0,1,2,...,n} is a subset of S-S, where S-S={abs(i-j) | i,j in S}.

Views

Author

Keywords

Comments

Examples

References

Crossrefs