Symmetries, asymmetries and sense of direction

Abstract

This thesis deals with problems related to the notion of sense of direction in graphs: We define this notion and provide some examples of labelling that realize it. We then survey the problem of minimal sense of direction in regular graphs using symmetric labelling, and its connection to various notions such as cycle symmetry, vertex symmetry, Cayley graph, view, and surrounding. We also present new types of symmetries that are equivalent to having minimal sense of direction. Afterward, we cover the problem of minimal sense of direction in regular graphs using an asymmetric labelling and establish several new results regarding this problem. We show that many classical topologies do not have asymmetric minimal sense of direction using the asymmetric labelling. We conclude this thesis with a program that finds the minimum chordal labelling in an arbitrary graph.