Recent advances on walks and trails problems in Temporal Graphs

Abstract

A temporal graph is a graph that lives in time, or in other words, a graph whose edges are available only at certain times. For instance, consider the public transportation network in a city. The stops can be seen as vertices in a graph which are linked through an edge at a given time if there is a bus linking them at such a time, according to the scheduling of the lines. In this scenario, the walks of interest are the ones that respect the flow of time, in the same way that, in order to catch a bus at a given time in a stop, we need to arrive there before the desired bus' departure.
Such a model has drawn extreme attention in the past years, and many works try to answer the fundamental question about “what is the right adaptation (and related problem’s complexity) to the temporal context of certain classic graph theory notions”. In this talk, I will present some recent results where co-authors  and myself investigated notions related to walks and trails in graphs. In particular, I will be talking about adapted concepts of: edge disjoint spanning branchings (Edmond's Theorem), Eulerian trails and walks (Euler’s Theorem), and disjoint walks and separators (Menger’s Theorem).

Further info available at:

https://www.combinatorics.org/ojs/index.php/eljc/article/view/v28i4p3
https://link.springer.com/chapter/10.1007/978-3-030-86593-1_21
https://link.springer.com/chapter/10.1007/978-3-030-79987-8_34