Tessellations on graphs: theory, algorithms, and complexity

Abstract

Due to recent technological advances, quantum computing has gained notoriety. In this paradigm, the concept of quantum walk is fundamental for the development of algorithms for quantum computers. Among the existing quantum walk models, the staggered model, proposed by Portugal et al. stands out, since it includes the Szegedy model as a particular case, and part of the coined model. The staggered model uses the concept of tessellations on graphs to generate the quantum evolution operators that perform the walker’s movements on the graph. Tessellations on graphs also have an interesting value for graph theory, since the parameter tessellation cover number T(G) is related to several other parameters present in the literature such as chromatic number, chromatic index, total chromatic number, independent set number, and clique number. In addition, problems related to T(G), such as t-tessellability, good tesellable recognition, and total good tessellable recognition have deep relations with classic problems in graph theory involving graph coloring. In this work we present results in graph theory for the problems related to tessellations on graphs mentioned above, such as computational complexity, lower and upper bounds for T(G), and the value of T(G) for several graph classes. Furthermore, we present a quantum walk model based on total tessellation cover, being pioneer in the use of vertices and edges as possible locations for the walker, simultaneously.