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 presented. By applying this model, integrity values are calculated for various graph families, and patterns within the results are identified. These patterns contribute to establishing boundaries or determining exact values of integrity for the analyzed graph families. The analyzed graph families encompass Glued Paths, generalized Theta graphs, (Double) Cone graphs, Fan graph, Lollipop graphs, generalized Barbell graphs, (Dutch) Windmill graphs, Paley graphs, and Kneser graphs. Additionally, two conjectures are formulated: one concerning a lower bound for the integrity of all Paley graphs, and another addressing the exact integrity values of specific Kneser graphs. The ILP model proves to be a valuable tool for further exploration of graph family integrity, offering opportunities for additional research and expanding our understanding of network robustness.

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 move. This enables us to prove results in different mathematical fields. We investigate three of them. The first one is from spectral graph theory: we prove the existence of a sharp κ-approximation for any graph. The second result is from linear algebra. It states that if a matrix has a high stable rank, it must contain a large column submatrix with large least singular value.   Lastly, the proof of the Kadison-Singer Problem is discussed. Despite being a problem from analysis, it was solved with the interlacing method, which is originally a method from discrete mathematics. This thesis shows how these three seemingly different problems are all connected by the same method, highlighting its advantages. The objective is to present a clear framework of the different facets of the interlacing method and provide an insight in the situations where one can expect the said method to be useful.

Constraint programming solvers provide a generalizable approach to finding solutions for optimization problems. However, when comparing the performance of constraint programming solvers to the performance of a heuristic solver for an optimization problem such as cluster editing, the heuristic solver is able to find near-optimal and optimal solutions much faster. The goal of this research is to understand how the behaviour of such a heuristic solver can assist the performance of constraint programming solvers in optimization problems. In order to achieve this, first Chuffed, a state-of-the-art constraint programming solver was combined with a heuristic approach to cluster editing, with the goal of emulating the performance of the heuristic algorithm, in particular, being able to find near-optimal solutions faster. Continuing, the goal was to generalize the behaviour observed by the modified solver, by emulating the performance observed without the need for the specialized heuristic solver. The generalized approach is tested on a wide variety of different tests. An approach to value selection was developed that performs lookahead propagations for the two values of a boolean variable and selects the value that has the most optimal solution within the domain after performing the lookahead propagation. This approach added a significant time overhead that increased the overall solving time for many problems, with the lookahead configuration having a median increase of 8.7% over the default configuration for the optimization problems of the MiniZinc Challenge 2022. However, it was able to successfully emulate the performance of the heuristic solver, finding near-optimal solutions significantly faster than the default value selection. In particular, for the optimization problems of the MiniZinc Challenge 2022, on average, the lookahead configuration had a definite integral for the time vs objective graph 54.7% lower than the default Chuffed configuration.

E-mobility, in particular electric vehicles (EVs), play a crucial role in the energy transition. While businesses are increasingly adopting EVs, there is still a lot of opportunity to grow. One aspect of this growth is the way these vehicles are used by companies, especially when it comes to the logistics of EV charging. To encourage companies to further reduce their carbon footprint by more efficiently utilizing EVs, this project proposes a combined vehicle routing and charging model. These models can be used separately, as well as together, allowing the charging model to be combined with any pre-existing routing engine. The goal of this project is to show the benefits of allowing EVs to be charged between shifts during the day, rather than exclusively overnight, as well as to show how such schedules can be made. Our results show that giving vehicles the opportunity to charge between shifts can significantly reduce the costs associated with fleet operations. If the fleet contains non-electric vehicles as well as electric ones, we also see a significant reduction in the number of kilometers driven using fossil fuels. When sufficient chargers were available, even when the vehicles had little time to charge, a feasible schedule could always be found. Moreover, when more realistic charging intervals were used, most vehicles were even able to fully recharge before the start of their next shift. Finally, we concluded that the set of chargers needed to find such a feasible schedule can be relatively small, meaning that even without extensive additions to the charging infrastructure, companies can still benefit from this policy change.

E-mobility, in particular electric vehicles (EVs), play a crucial role in the energy transition. While businesses are increasingly adopting EVs, there is still a lot of opportunity to grow. One aspect of this growth is the way these vehicles are used by companies, especially when it comes to the logistics of EV charging. To encourage companies to further reduce their carbon footprint by more efficiently utilizing EVs, this project proposes a combined vehicle routing and charging model. These models can be used separately, as well as together, allowing the charging model to be combined with any pre-existing routing engine. The goal of this project is to show the benefits of allowing EVs to be charged between shifts during the day, rather than exclusively overnight, as well as to show how such schedules can be made. Our results show that giving vehicles the opportunity to charge between shifts can significantly reduce the costs associated with fleet operations. If the fleet contains non-electric vehicles as well as electric ones, we also see a significant reduction in the number of kilometers driven using fossil fuels. When sufficient chargers were available, even when the vehicles had little time to charge, a feasible schedule could always be found. Moreover, when more realistic charging intervals were used, most vehicles were even able to fully recharge before the start of their next shift. Finally, we concluded that the set of chargers needed to find such a feasible schedule can be relatively small, meaning that even without extensive additions to the charging infrastructure, companies can still benefit from this policy change.

During this research, we investigate if there exists a k(n)-core in the scale-free configuration model, this is a commonly used null model to simulate networks. The scale-free configuration model produces a random graph, where the degree of every vertex is determined using a random variable. In this thesis, the discrete Pareto variable is used with parameter τ ∈ (2, 3). The k-core of a graph is the biggest induced subgraph where every vertex is connected to at least k edges in the subgraph. In this thesis, we let k be dependent on the number of vertices in a graph, this makes it a k(n)-core. By investigating whether k(n)-cores exist in graphs produced by the scale-free configuration model, we hope to to get a better understanding of the structure of these graphs. In this thesis, the scale-free configuration model is modeled as a death process. This death process will produce the graph and its k(n)-core jointly. First, we remove all edges which cannot be part of the k(n)-core until the point where no such edges exist anymore. This is the moment where we reach the k(n)-core. Using this method, we prove that whenever the number of vertices is sufficiently high a (log(n))^α-core exists with high probability for all constant α >0. For α < (3−τ)/(8τ) , also a n^α-core exists with high probability when the number of vertices is sufficiently high. We also find a lower bound for the number of vertices and edges left in the cores.

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 focus of this research, which we end up succeeding in by giving a counter-example, thus disproving the conjecture. We do this by first showcasing some relevant background knowledge from game theory in chapter 1. In chapter 2 we then introduce the Game of Cycles and its rules, as well as some of the previous results others have found. We continue in chapter 3 by creating a python script to brute-force the game for us and it is here that we find a counter-example to the main conjecture, of which we prove that it is indeed a counter-example. We close off with chapter 4 by looking at a simplification of the game, where it is played on trees instead of any graph. Here we prove that the main conjecture does hold for a special family of trees and state a conjecture for the solution of any tree.

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 sensors k, the algorithm finds the k-truncated metric dimension of that tree. The algorithm presented in this thesis is a modification of the algorithm given by Gutkovich and Song Yeoh [6]. The algorithm in this thesis improves on their algorithm in both validity and time complexity. We show that given any tree and any value k, the algorithm returns a k-resolving set for that tree. Moreover, we conjecture the difference in the k-truncated metric dimension of any tree and the size of the k-resolving set found by the algorithm for that tree is never greater than one. The time complexity of the algorithm is proven to be O(k3n), where k is the measuring range of the sensors and n is the number of vertices in the tree. This implies that the time complexity is linear in n for fixed k.

Out of Home advertising is traditional outdoor advertising. Over the last decade the digital Out of Home advertising possibilities have grown substantially. These possibilities include hour-based advertisement schedules, rapidly implemented changes to advertisements and obtaining location data from consumers being exposed to advertisements. Investigating these possibilities further for improving customer engagement and optimising target group reach is of great importance in marketing and marketing science. This thesis will focus on exposure data obtained from vehicle locations in central London. Using this data we want to model the frequency with which individuals see advertisements and research the overlap in exposures of individuals to multiple media vehicles where advertisements are displayed. We focus on modelling exposures of individuals to two vehicles, comparing different types of bivariate distributions. In this thesis we present the comparison of two models: an adapted version of the Sarmanov bivariate distribution and copulas. We refer to these models as the Danaher and Copula model respectively. The fitting and simulations of the models are based on bivariate data of two specified vehicles, to be able to comment on the overlap between these vehicles. To investigate the performance of the models all combinations of vehicles are modelled after which the results are combined. Both models simulate small frequencies of exposures of individuals adequate, but for more extreme values both models fail to represent the observed data. Especially the simulation of overlap is done poorly by the models. Several approaches have been tried to improve the models' performance, without much success. The analysis shows that the data at hand requires more sophisticated methods to handle joint exposure and more research needs to be done. In addition the variable distance is added to the research problem, which intuitively has great influence on the overlap between media vehicles. This is done by using 3-dimensional copulas. For this research we modify the data: instead of first fitting and simulating a copula model on the data of two vehicles and then combining the results of all vehicle combinations, we first combine the data from all the combinations of vehicles and repeat the fitting procedure thereafter. Several options for the modelling of these copulas are presented. Similar analysis shows, again, that the nature of the data requires more complex models to handle the overlap while also accounting for the vehicle distance. Finally, using the modified data we look back at the 2-dimensional copula model and perceive an excellent resemblance of the data for the Student-t copula.

A code C is defined to be a set of S words, where a word is a sequence of n entries. We call S the size and n the length of the code. The entries of the code can have k different values, {0, .., (k − 1)}. Define a perfect k-hash code (PHC) as a code with the property that any collection of v words in the code is different at at least one index. PHC’s are useful mathematical objects within different fields of theoretical computer science and coding theory. This thesis will focus on one typical kind of PHC, a trifferent code. Such a trifferent code is defined as a PHC where k = v = 3. This means that any collection of three words in the code has to differ at some index. We now define T (n) to be the largest possible size of a trifferent code given that it has length n. The question that arises is, what is the value of T (n)? It turns out that determining the exact value is complicated, unless n is really small. Therefore, we try to understand the asymptotic nature of the function T (n). This is what we call the trifference problem. This paper will cover and prove the best known asymptotic upper and lower bound on T (n). Moreover, it will explain and include a Python code that can be used to show and prove all values of T (n) for n ∈ {1, .., 6}. Lastly, two different ways to explicitly construct trifferent codes for any value of n will be given and compared.

In this thesis, we consider the threshold metric dimension problem of graphs, related to and motivated by source detection. We construct a graph G = (V,E) for a given set of sensors of size m: {s1, s2, ..., sm} and a range k > 0. We want that each node v ∈ V has a unique combination of distances (dk (s1, v),dk (s2, v), ...,dk (sm, v)), where dk is the distance function in a graph limited by the range k (the distance is denoted as being ∞ if the distance is larger than k). Our aim in this thesis is to construct such a graph that is extremal in size, that is: the vertex set V is as large as possible. We shall give such constructions with proof for optimality up to k = 3 and general m and a different construction with incomplete proof for optimality for general k and m. For any construction we will prove that each vertex is uniquely identified. Furthermore, we will compare our results to another paper with a similar conclusion about the extremal size of graphs with metric dimension m and a given diameter D.

A set of lines passing through the origin in Euclidean space is called equiangular if the angle between any two lines is the same. The question of finding the maximum number of such lines, N(d) in any dimension d is an extensively studied problem. Closely related, is the problem of finding the maximum number of lines, N_α(d), such that the common angle between the lines is arccosα. In recent years, many progress has been made on this problem. We review some of these breakthrough results and the techniques they use to approach this problem. The first main result is a linear upper bound on N_α(d) which is found using a completely novel approach with respect to techniques used in previous works. Another main result that we discuss solves the problem of finding N_α(d) for high enough dimensions. Some classic results from some of the first studies on equiangular lines are also discussed. Finally, some suggestions are given for possible further research.

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 investigate the relation between the cop number of the Erdős-Rényi (ER) random graph G(n, p_n) and compare it to another graph parameter, the domination number. Our goal is to collect results from previous research and create an overview. Throughout this thesis, we provide some examples of graphs for which the cop number is equal to the domination number. Furthermore, we provide proofs for some results on the domination number of the ER random graph. The main takeaway is that the cop number is asymptotic to the domination number for particular values of p_n.

In this thesis, we examine the kernel-based spatial random graph (KSRG) model, which is a generalisation of many known models such as long-range percolation, scale-free percolation, the Poisson Boolean model and age-based spatial preferential attachment. We construct a KSRG from a vertex set V = Z^d, assigning each vertex v ∈ V a weight Wv according to a power-law with parameter τ − 1 and connecting each pair of vertices conditionally independently according to P(u ↔ v|Wu,Wv) = Θ(1 ∧(max {Wu,Wv}^(σ1) min {Wu,Wv}^(σ2)/|u − v|^d))^α. Our first contribution is to show that, under certain choices of the parameters σ1, σ2, τ and α, the graph distance is at most poly-logarithmic or at most doubly logarithmic when compared to the spatial distance. Furthermore, the parameters σ1 and σ2 allow for extra degrees of freedom when compared to the models mentioned earlier, which yields a new exponent for poly-logarithmic distances and a generalised constant for doubly logarithmic distances. Our second contribution lies in the techniques used to prove these results. In particular, we show that with probability tending to 1 there is a subset of vertices that behaves pseudo-randomly with regards to the expected amount of vertices with a given weight in any radius. The presence of this subset, which we call a net, allows for the avoidance of the use of FKG-like inequalities in proofs. Primarily, it allows us to reveal all relevant weights in advance, which allows us to disregard many correlations that we would otherwise need to take into account during construction of paths.

Consider an arbitrary finite grid in some field. How many hyperplanes are required so that every point is contained in at least k hyperplanes, except for one point that is not allowed to be contained in any hyperplane? To solve this so-called hyperplane grid covering problem, the polynomial method has proven to be extremely useful in finding bounds on the minimum number of hyperplanes required. This has given rise to a second problem: the polynomial grid covering problem. This problem considers the minimum degree of a polynomial such that every grid point is a root with multiplicity k, except for one point where the polynomial does not vanish. We study these two related problems for multiple grids: the hypercube, the vector space over the binary field and grids in the Cartesian plane. Since polynomial covers in the latter have not been studied before, we provide algorithms and techniques to study these covers. We also explore the link between grid coverings and two results from algebraic geometry: the Footprint Bound and the Cayley-Bacharach Theorems.