4 papers
Structural parameterizations of Geodetic Set on directed (acyclic) graphs
Laurent Beaudou, Florent Foucaud, Lucas Lorieau +1
In DIRECTED GEODETIC SET, we are given a (directed) graph and seek a small solution set such that every vertex lies on a shortest directed path between two verti…
Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
Laurent Beaudou, Jan Bok, Florent Foucaud +2
The \emph{-neighbourhood complexity} of a graph is the function counting, for a given integer , the largest possible number, over all vertex-subsets of size , of s…
Splitting vertices of bipartite graphs preserves de Bruijn-ErdÅs property
Laurent Beaudou, Guillermo Gamboa Quintero
In this note, we prove that every graph obtained from a bipartite graph by iteratively splitting vertices into two adjacent twins has the de Bruijn-ErdÅs property.
The Canadian Traveller Problem on outerplanar graphs
Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev +5
We study the -Canadian Traveller Problem, where a weighted graph with a source and a target are given. This problem also has a hidden input $E_* \…