Spanning Trees and Graphs Embedded in Surfaces To what extent is a graph determined by the trees contained in it? That is, if we know the edge sets of each of the spanning trees (i.e., maximal acyclic subgraphs) in a connected graph, then do we know the graph itself? It only takes a little bit of thought to see that the answer is "no" (e.g., suppose the graph is a tree).  But this “no” is really a “more or less,…

Robustness of Complex Networks Network Science aims to understand the graph structure of networks and the dynamic processes that take place on networks. Examples of processes on networks are transport of items (IP packets with digitalized  information, cars, containers) and diffusion (epidemics, electric current, water flows, human emotions). The Network Architectures and Services Section at the Delft University of Technology contributes to the fundaments of Network Science: we investigate amongst others geometric representations of networks, epidemic spread on networks, spectra of  graphs and network algorithms. In addition, we…

Mutually Orthogonal Cycle Systems A $k$-cycle system of order $n$ is a set of $k$-cycles whose edges partition the edge set of $K_n$.  We say that two cycle systems $\mathcal{C}$ and $\mathcal{C}'$ are {\em orthogonal} if every cycle in $\mathcal{C}$ shares at most one edge with each cycle in $\mathcal{C}'$.  Orthogonal cycle systems arise naturally from simple Heffter arrays and biembeddings of cycle decompositions. A collection of cycle systems is {\em mutually orthogonal} if any two of the systems are…

The Orthogonal Colouring Game The Orthogonal Colouring Game is a combinatorial game in which two players alternately colour vertices of a pair of isomorphic graphs while respecting the properness and the orthogonality of the colouring. Each player aims to maximize her score, which is the number of coloured vertices in the copy of the graph she owns. An involution $\sigma$ of a graph $G$ is strictly matched if its fixed point set induces a clique and any non-fixed point $v \in V(G)$ is connected with its…

Reconfiguration for Dominating Sets Given a problem and a set of feasible solutions to that problem, the associated  reconfiguration problem involves determining whether one feasible solution to the original problem can be transformed to a different feasible solution through a sequence of allowable moves, with the condition that the intermediate stages are also feasible solutions.  Any reconfiguration problem can be modelled with a  reconfiguration graph, where the vertices represent feasible solutions and two vertices are adjacent if and only if…