Necessary conditions on graceful labels: A study case on trees and other examples

Abstract

Necessary conditions on the labels of a graceful graph are hardly present in the literature, the major and isolated result being Rosa's theorem dated 1966, which rules out a large class of Eulerian graphs. Here we present a counting technique which generalises Rosa's, and we apply it to point out some constraints on the labels of a selected class of graceful trees. The counting functions we employ are the first four elementary symmetric functions. In the end we also provide an alternative proof of the non-gracefulness of some complete graphs. Among other things, these constraints may reduce the search of graceful labellings by a computer or a human being.