|
%I M2526 #97 Oct 14 2023 23:46:31
%S 0,1,3,6,9,13,17,23,29,36,43,50,58,68,79,90,101,112,123,138,153,168,
%T 183,198,213,232
%N Maximal number of edges in a graceful graph on n nodes.
%C 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.
%C 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.
%C 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
%C 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]
%D 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.
%D 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.
%D 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.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H D. Beutner and H. Harborth, <a href="https://doi.org/10.1007/BF03322754">Graceful labelings of Nearly Complete Graphs</a>, Results Math. 41 (2002) 34-39.
%H G. S. Bloom and S. W. Golomb, <a href="https://doi.org/10.1109/PROC.1977.10517">Applications of numbered undirected graphs</a>, Proc. IEEE 65 (1977), 562-570.
%H G. S. Bloom and S. W. Golomb, <a href="https://doi.org/10.1007/BFb0070364">Numbered complete graphs, unusual rulers, and assorted applications</a>, Theory and Applications of Graphs, Lecture Notes in Math. 642, (1978), 53-65.
%H L. Egidi and G. Manzini, <a href="http://www.di.unipmn.it/TechnicalReports/TR-INF-2011-06-01-UNIPMN.pdf">Spaced seeds design using perfect rulers</a>, Tech. Rep. CS Department Universita del Piemonte Orientale, June 2011.
%H P. Erdős, <a href="https://www.renyi.hu/~p_erdos/1980-03.pdf">A survey of problems in combinatorial number theory</a>, Ann. Discrete Math. 6 (1980), 89-115.
%H P. Erdős and R. Freud, <a href="http://dx.doi.org/10.1016/0022-314X(91)90083-N">On sums of a Sidon-sequence</a>, J. Number Theory 38 (1991), 196-205.
%H P. Erdős and P. Turán, <a href="http://www.renyi.hu/~p_erdos/1941-01.pdf">On a problem of Sidon in additive number theory, and on some related problems</a>, J. Lond. Math. Soc. 16 (1941), 212-215.
%H J. Leech, <a href="https://doi.org/10.1112/jlms/s1-31.2.160">On the representation of 1, 2, ..., n by differences</a>, J. Lond. Math. Soc. 31 (1956), 160-169.
%H S. Lou and Q. Yao, <a href="http://hrj.episciences.org/124">A Chebyshev's type of prime number theorem in a short interval II</a>, Hardy-Ramanujan J. 15 (1992), 1-33.
%H Peter Luschny, <a href="http://www.luschny.de/math/rulers/prulers.html">Perfect Rulers</a>.
%H Peter Luschny, <a href="http://www.luschny.de/math/rulers/optimalconjecture.html">Wichmann Rulers</a>.
%H Klaus Nagel, <a href="http://www.luschny.de/math/rulers/kamm.txt">Evaluation of perfect rulers</a> C program.
%H O. Pikhurko, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.003">Dense edge-magic graphs and thin additive bases</a>, Discrete Math. 306 (2006), 2097-2107.
%H O. Pikhurko and T. Schoen, <a href="http://www.emis.de/journals/INTEGERS/papers/h11/h11.Abstract.html">Integer Sets Having the Maximum Number of Distinct Differences</a>, Integers: Electronic journal of combinatorial number theory 7 (2007).
%H I. Redéi and A. Rényi, <a href="http://mi.mathnet.ru/eng/msb5985">On the representation of integers 1, 2, ..., n by differences</a>, Mat. Sbornik 24 (1949), 385-389 (Russian).
%H Arch D. Robison, <a href="http://software.intel.com/articles/parallel-computation-of-sparse-rulers">Parallel Computation of Sparse Rulers</a>, Jan 14 2014.
%H F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, <a href="https://dx.doi.org/10.21227/cd4b-nb07">MRLA search results and source code</a>, Nov 6 2020.
%H F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, <a href="https://doi.org/10.1109/OJAP.2020.3043541">Large Minimum Redundancy Linear Arrays: Systematic Search of Perfect and Optimal Rulers Exploiting Parallel Processing</a>, IEEE Open Journal of Antennas and Propagation, 2 (2021), 79-85.
%H J. Singer, <a href="http://dx.doi.org/10.1090/S0002-9947-1938-1501951-4">A theorem in finite projective geometry and some applications to number theory</a>, Trans. Amer. Math. Soc. 43 (1938), 377-85.
%H David Singmaster, David Fielker, N. J. A. Sloane, <a href="/A004116/a004116.pdf">Correspondence, August 1979</a>.
%H M. Wald & N. J. A. Sloane, <a href="/A005318/a005318_3.pdf">Correspondence and Attachment, 1987</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GracefulGraph.html">Graceful Graph</a>.
%H B. Wichmann, <a href="http://jlms.oxfordjournals.org/content/s1-38/1/465.extract">A note on restricted difference bases</a>, J. Lond. Math. Soc. 38 (1963), 465-466.
%H Al Zimmermann's Programming Contests, <a href="http://azspcs.net/Contest/GracefulGraphs">Graceful Graphs</a>, September - December 2013.
%F a(n) = n*(n-1)/2 - A212661(n). - _Kellen Myers_, Jun 06 2016
%e 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.
%e 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.
%o (C) See Klaus Nagel link.
%o (Parallel C++) See A. Robison link.
%Y Cf. A046693, A103294, A103298, A103299, A103296, A102508, A212661.
%Y A080060 is an erroneous version of the sequence, given in Bermond's paper. Cf. A005488.
%Y A289761 provides the conjectured continuation.
%K nonn,nice,hard,more
%O 1,3
%A _N. J. A. Sloane_, _Simon Plouffe_
%E 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.
%E Edited by _Dean Hickerson_, Jan 26 2003
%E 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.
%E Using this program _Hugo Pfoertner_ found further evidence for the conjectured term a(21)=153, Feb 23 2005
%E Terms a(21) .. a(24) proved by exhaustive search by Arch D. Robison, _Hugo Pfoertner_, Nov 01 2013
%E Term a(25) proved by exhaustive search by Arch D. Robison, _Peter Luschny_, Jan 14 2014
%E Term a(26) proved by exhaustive search by Fabian Schwartau, _Yannic Schröder_, Lars Wolf, Joerg Schoebel, Feb 22 2021
|
