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

[Bhaskar Bagchi]

Yes, if only a subset of {1,2,...,n} was used as labels then the resulting
graph would be graceful, but neither a tree nor a graph of order n. One of
the equivalent definitions of a tree is that it is a connected graph whose
number of edges is exactly one short of its number of vertices.

On Sat, Nov 21, 2020 at 2:59 AM Marc LeBrun <mlb at well.com> wrote:

> 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/
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>