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…

In this talk, I will show regions that contain no complex zeros the edge-cover polynomials of hypergraphs. The edge cover polynomial of a graph $G$ is the generating function of edges that covers $V(G)$. It is known that the zeros of this polynomial have length at most $\frac{(2+\sqrt{3})^2}{1+\sqrt{3}}$, that we strengthen by showing that it is at most $4$.  We use the general subgraph counting polynomial of Wagner to establish this result along with its generalization for the edge cover…

About a year ago Jason Brown spoke in our seminar (of the university of Amsterdam) about the two-terminal reliability polynomial and left us with some questions about the closure of the complex zeros of all such polynomials (the zero-locus). In this talk I will define a way to capture, for a certain parameter, whether the set of all two-terminal reliability polynomials behaves chaotically around this parameter or not, i.e. whether this parameter is active or passive. I call the set…

We study the algebraic connectivity for several classes of random semi-regular graphs. For large random semi-regular bipartite graphs, we explicitly compute both their algebraic connectivity and as well as the full spectrum distribution. For an integer d in , we find families of random semi-regular graphs that have higher algebraic connectivity than a random d-regular graphs with the same number of vertices and edges. On the other hand, we show that regular graphs beat semi-regular graphs when d >8. More…