[seqfan] Re: item A213058 of O.E.I.S.

[Marc LeBrun]

Brendan, thanks for the clarification!  That all makes sense, and Bhaskar's definition is good.

Sorry, I was faked out by the diagram on that page, which omits the vertex label "2".

(Also ironic, in today's Covidian context, is the Wiki's comment that "Kotzig once called the effort to prove the [graceful tree] conjecture a ''disease''."!)


> On Nov 20, 2020, at 12:49 PM, Brendan McKay <Brendan.McKay at anu.edu.au> wrote:
> 
> Marc, if you are referring to https://en.wikipedia.org/wiki/Graceful_labeling ,
> the definition agrees for trees. The vertex labels must be distinct numbers
> from {0,1,...,m} where m is the number of edges.  For n-vertex trees, m=n-1
> so all the numbers from 0 to n-1 must be used.  Clearly it doesn't matter if
> 0..n-1 or 1..n is used.
> 
> It would be great to prove this conjecture about A213058, but I don't think
> that that would help to solve the graceful tree conjecture.
> 
> Meanwhile, the number of graceful labellings of a path is still unknown,
> see A006967.
> 
> Cheers, Brendan.
> 
> On 21/11/20 5:47 am, Marc LeBrun wrote:
>> Bjaksar, sounds interesting!  Better editors please correct me, but I'll make a few quick comments:
>> 
>> *  OEIS entries should be plain ASCII text (although links to PDFs may also be included)
>> 
>> *  A comment stating a conjecture is fine; there are many examples in the OEIS you can follow.  It's probably best to begin your text with the label "Conjecture:..."
>> 
>> *  I'm not familiar with graceful trees, but the definition you give in this email seems to differ slightly from Wikipedia's in that yours seems(?) to say that the vertexes are labeled with the full set {1,2,...n} but some of Wikipedia's examples use only a subset.  To avoid confusion we should make sure that any definition of graceful tree we give is precise (or if, unfortunately, there's more than one in use, that this is indicated).
>> 
>> *  Wikipedia also mentions that enumerations up to at least n=29 have been published.  Have these values been verified to match A213058?  If so, bibliographic references links to those published values should also be included.
>> 
>> It would be exciting if the OEIS can help resolve these conjectures!
>> 
>> 
>>> On Nov 20, 2020, at 5:53 AM, Bhaskar Bagchi <bhaskarbagchi53 at gmail.com> wrote:
>>> 
>>> Hello,
>>> I wish to post in O.E.I.S. the following comment on this sequence. In case
>>> this is not the correct format for a post (for instance, if you require a
>>> p.d.f.), please let me know.
>>> 
>>> A gracefully labelled tree of order n is a connected graph T with vertex
>>> set {1,2, ...,n} with the property that , for every element k of
>>> {1,2,...,n-1}, there is a unique edge {i,j} of T such that |i-j|=k. We do
>>> not identify isomorphic trees.  I want to conjecture :
>>> for every n, the total number of gracefully labelled trees of order n is
>>> the nth term of the sequence A213058.
>>> 
>>> As far as I can see, no such combinatorial description of this sequence is
>>> presently known; it is described by a functional equation for its
>>> exponential generating function (which is tantamount to a recurrence
>>> relation). An affirmative resolution of my conjecture is likely to yield an
>>> extremely efficient algorithm for recursively enumerating the gracefully
>>> labelled trees. This in turn should be a great step towards proving the
>>> well known conjecture that all trees can be gracefully labelled.
>>> 
>>> With best regards,
>>> Bhaskar Bagchi
>>> 
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>> 
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/