Forbidden Patterns in Temporal Graphs Resulting from Encounters in a Corridor

M Habib, MH Nguyen, M Rabie, L Viennot - International Symposium on …, 2023 - Springer
International Symposium on Stabilizing, Safety, and Security of Distributed …, 2023Springer
In this paper, we study temporal graphs arising from mobility models where some agents
move in a space and where edges appear each time two agents meet. We propose a rather
natural one-dimensional model. If each pair of agents meets exactly once, we get a simple
temporal clique where each possible edge appears exactly once. By ordering the edges
according to meeting times, we get a subset of the temporal cliques. We introduce the first
notion of forbidden patterns in temporal graphs, which leads to a characterization of this …
Abstract
In this paper, we study temporal graphs arising from mobility models where some agents move in a space and where edges appear each time two agents meet. We propose a rather natural one-dimensional model.
If each pair of agents meets exactly once, we get a simple temporal clique where each possible edge appears exactly once. By ordering the edges according to meeting times, we get a subset of the temporal cliques. We introduce the first notion of forbidden patterns in temporal graphs, which leads to a characterization of this class of graphs. We provide, thanks to classical combinatorial results, the number of such cliques for a given number of agents.
Our characterization in terms of forbidden patterns can be extended to the case where each edge appears at most once. We also provide a forbidden pattern when we allow multiple crossings between agents, and leave open the question of a characterization in this situation.
Springer