Labelling Problems on Graphs

Abstract

This is the postdoctoral research project of Atílio Gomes Luiz, to be carried out under the supervision of Professor Yoshiko Wakabayashi at the Institute of Mathematics and Statistics of the University of São Paulo. This project addresses topics in Graph Theory, more specifically, graph labelling problems. Graph labelling is the assignment of labels, usually nonnegative integers, to the elements (vertices or edges, or both) of a graph, subject to certain conditions. There are several labelling problems on graphs, and what sets them apart are the objects that are labelled, and the properties the assigned labels have to satisfy. Well-known problems such as vertex (or edge) coloring of a graph are also labelling problems. Most graph labelling problems were motivated by practical applications, such as allocation of radio frequencies to transmitters, assignment of error-correcting codes to computer chips, and optimalcircuit design. Moreover, some labellings are also used as tools to investigate other problems, such as graph decomposition. This postdoctoral research project addresses the investigation of three graph labelling problems, which are interesting and relevant both from practical and theoretical point-of-view. These are: L(2,1)-labelling, the graceful labelling and the edge-magic labelling of graphs.