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...

Reconfiguration of Graph Colorings

For this thesis, we consider two $k$-colorings of a graph $G$ adjacent if one can recolor one into the other by changing the color of one vertex. The reconfiguration graph of a graph $G$ on $k$ colors $\mathcal{C}_{k}(G)$ is the graph for which the vertices are the $k$-colorings of $G$, and an edge is between two $k$-colorings if they are...

A Note on Integrity: ILP Modelling and Analysis on Graph Families

This thesis provides a fresh perspective on the (vertex) integrity of graphs, serving as a measure of network robustness. The study begins by introducing fundamental concepts and methods for evaluating the integrity of different graph families. An Integer Linear Programming (ILP) model, specifically designed for assessing integrity, is then...

The "Number Hides Game" on a Tree: A bachelor thesis in game theory

The "Number Hides Game" (NHG) is 2-player game played on a board that consists of a row of p consecutive coins. Player I and player II simultaneously choose subsets of m and n consecutive coins respectively. Player II pays the number of coins that lie in the intersection of the subsets to player I. This thesis introduces basic knowledge from the...

Extremal graphs for threshold metric dimension

In this thesis, we consider the threshold metric dimension problem of graphs, related to and motivated by source detection.<br/>We construct a graph G = (V,E) for a given set of sensors of size m: {s1, s2, ..., sm} and a range k &gt; 0. We want that each node v ∈ V has a unique combination of distances (dk (s1, v),dk (s2, v), ...,dk (sm, v)),...

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...

Counting matchings in cubic graphs

This bachelor thesis concerns the proof of Esperet et al. of the Lov ász-Plummer conjecture, which states that a cubic bridgeless graph has exponentially many perfect matchings. The first part of this thesis treats the concepts used in this proof. By means of examples, small proofs and a structural overview, this proof is made more accessible....