Dipartimento di Scienze di Base e Applicate per l'Ingegneria

Aula 2E Pal. RM004

Andrea Vietri (Sapienza Università di Roma)

Graceful polynominals: an introduction and a glance at the graceful tree conjecture.

I will introduce a family of homogeneous polynomials for any given graph, with coefficients (mod 2), one for every degree and with as many variables as the number of vertices. These polynomials are related to graceful labellings: in some cases a graceful polynomial that vanishes (mod 2) could be an efficient tool for proving that the graph is non-graceful, in the same spirit as in a pioneering work by A. Rosa. More generally, graceful polynomials provide necessary conditions for gracefulness.