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

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

Real Equiangular Lines

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

The Trifference Problem

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

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

Hyperplane covering problems