8 problems

A weakly separating path system of a graph is a family of paths that weakly separates its edge set. Motivated by a question of Katona, Falgas-Ravry, Kittipassorn, Korandi, Letzter…

Let $H$ be a graph with at least one edge. A subdivision of $H$ is obtained by replacing edges of $H$ with pairwise internally vertex-disjoint paths; let $\operatorname{Sub}(H)$ be…

Let $H$ and $G$ be graphs. A subdivision of $H$ is a graph obtained from $H$ by replacing edges with internally vertex-disjoint paths. An $H$-separating system of $G$ is a family o…

Let $G$ be a graph on $n$ vertices. A path separating system of $G$ is a collection of paths in $G$ such that, for every ordered pair of distinct edges $(e,f)$, some path contains…

Let $G$ be a graph. A path system of $G$ is a set of paths in $G$. It is weakly separating if for every pair of edges of $G$ there exists a path in the system that contains exactly…

Linear-size separating path systems conjecture. Every $n$-vertex graph $G$ admits weak- and strong-separating path systems of size linear in $n$:

Let $G$ be an $n$-vertex graph, and let $\operatorname{sp}(G,E)$ denote the minimum size of an edge-separating family of paths in $G$. Define … where the maximum is over all $n$-ve…

Let $G$ be a graph on $n$ vertices. A strongly-separating path system is a collection of paths in $G$ such that, for every two distinct edges $e$ and $f$ of $G$, there are paths…