Title: Path decompositions of random directed graphs In this talk we consider the problem of partitioning the edges of a digraph into as few paths as possible. The minimum number of paths needed in such an edge decomposition is called the path number of the digraph. The problem of determining the path number is generally NP-hard. However, there is a simple (easy to compute) lower bound for the path number of a digraph in terms of its degree sequence, and…

Improved bounds for zeros of the chromatic polynomial on bounded degree graphs About 20 years ago Sokal proved that there exists a constant C so that for any graph G, all of the complex zeros of its chromatic polynomial are contained in the disk of radius C Delta(G) centered at 0. (Here Delta(G) denotes the maximum degree of G.) He showed that C could be taken slightly smaller than 8. This was improved to 6.91 by Fernández and Procacci. In this…

2017 saw the centennial of William Tutte, one of the greatest mathematicians of modern times.  One of the testimonies to Tutte’s genius is that nearly everything he did proved to be a catalyst, triggering an explosion of further investigations and opening whole new vistas of mathematics.  The Tutte polynomial is one of many such examples in his legacy.   Here we will explore some of its salient properties and some of the many directions that propagated outward from the original Tutte…

I will discuss a few examples where considering loops leads to interesting insights, often allowing unifying existing results. These examples will include cops and robbers games, graph homomorphisms, variants of interval and chordal graphs, and versions of domination. Join Zoom Meeting: link

There are many results about triangles in graphs, but the property that every edge in a graph is in at least one triangle seems not to have been studied before. The 4-regular case was quickly solved collaboratively following an internet posting and then written about by one author in their blog, before being published in the Journal of Graph Theory in 2013. However, the result that was originally wanted was a characterisation for 5-regular graphs, and that did not emerge…

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…