Algorithm for k-truncated metric dimension of trees

The k-truncated metric dimension of a graph is the minimum number of sensors (a subset of the vertex set) needed to uniquely identify every vertex in the graph based on its distance to the sensors, where the sensors have a measuring range of k. We give an algorithm with the goal that given any tree and any value for the measuring range of the...

On the Dual of the Lovász Theta Prime Number for the Disjunctive Product of Graphs

The Lovász theta function, and the variants of it given by Schrijver and Szegedy are upper bounds on the independence number of a graph. These functions play an important role in several optimization problems, such as the Cohn-Elkies bound for optimal sphere packing densities.<br/><br/>This thesis covers the properties of these functions. The...

The Game of Cycles

The Game of Cycles, invented by Francis Su (2020, p.51) is an impartial game played on a graph, where players take turns marking an edge according to a set of rules. Together with the game, there also came a conjecture that gives a condition for whether a specific position is winning or losing. Proving or disproving this conjecture is the main...

Controlling the behaviour of eigenvalues: The interlacing method

This thesis uses the method of interlacing polynomials to study the behaviour of eigenvalues of a matrix after a rank-one update. Specifically, interlacing polynomials, common interlacing and interlacing families are exhaustively studied. These are excellent tools to find bounds on the eigenvalues of updated matrices by keeping track of how they...

On the domination number and cop number of Erdős–Rényi random graphs

We consider the game cops and robbers, which is a pursuit-evasion game played on a graph G. The cops and the robber take turns moving across the vertices of G, where the goal for the cops is to eventually catch the robber. Specifically, we study the cop number of G, i.e. the minimum number of cops that is needed to catch the robber on G. We...

The influence of location on the profitability of a charging station

With the increasing number of electric vehicles on the road, the routing problem has become more complex. As charging electric vehicles takes longer than fueling non-electric vehicles, congestion can occur at charging stations. This might lead to the shortest route not being the fastest route, due to long waiting times at the stations. By...

The lattice graph's Pfaffian orientations, planar and toroidal

In 1961 Kasteleyn solved the dimer problem. With the use of Pfaffans he managed to find a formula to enumerate the number of perfect matchings on a lattice graph. In this thesis we take another look at the methods Kasteleyn used. Besides that, we proof that for an m × n lattice graph on the torus, where m and n are even, there does not exist a...