Sailing towards, and then against, the graceful tree conjecture: some promisuous results. (English) Zbl 1163.05007
Summary: The graceful tree conjecture is getting old – though 40 years are not so many – while researchers from all over the world keep on trying to put an affirmative end to it. Kotzig called a disease the effort of proving it. In this paper we fall into the opposite disease, by shyly moving towards the search of a tree that is not graceful. Our first result, on suitable attachments of graceful trees, does actually produce new graceful trees. But the reader might perceive a subtle friction between the combinatorial structure and the arithmetical need of achieving a graceful labelling (that sensation sound perhaps like a warning). Subsequently, the classification of all graceful labellings for a rather simple class of trees seem at a first glance reassuring for its richness, while a more careful analysis may highlight some heavy constraints for labels, due to the mere structure of trees. Here the question is: what could happen to label constraints if the tree has a wilder structure? Should we give up gracefulness? In the end we turn our cards over and introduce a polynomial associated to a given tree, which is expected to help the willing researcher to find some ungraceful tree, if any, in the next future.