Skip to main content
edited body
Source Link
Agelos
  • 1.9k
  • 10
  • 17

Menger's theorem says that the maximum number of pairwise disjoint paths between two vertex sets $L,R$ of a graph G equals the minimum size of an $L$-$R$ separator. Below is a generalisation with more than two vertex sets, arranged in a liner fashion, and a set of paths that simultaneously saturates all pairs of these vertex sets. The question is if this is known:

enter image description hereenter image description here Let $G$ be a finite graph, and $L_i, 0 \leq i \leq n$, a family of disjoint vertex sets of $G$, such that each $L_i, 0 < i < n$ separates $L_{i-1}$ from $L_{i+1}$. Let $k_{i,j}$ denote the maximum number of pairwise disjoint $L_i$-$L_j$ paths. Then there is a set $\mathcal{P}$ of pairwise disjoint paths in $G$, such that for every $0\leq i<j \leq n$, at least $k_{i,j}$ elements of $\mathcal{P}$ meet both $L_i$,$L_j$.

Menger's theorem says that the maximum number of pairwise disjoint paths between two vertex sets $L,R$ of a graph G equals the minimum size of an $L$-$R$ separator. Below is a generalisation with more than two vertex sets, arranged in a liner fashion, and a set of paths that simultaneously saturates all pairs of these vertex sets. The question is if this is known:

enter image description here Let $G$ be a finite graph, and $L_i, 0 \leq i \leq n$, a family of disjoint vertex sets of $G$, such that each $L_i, 0 < i < n$ separates $L_{i-1}$ from $L_{i+1}$. Let $k_{i,j}$ denote the maximum number of pairwise disjoint $L_i$-$L_j$ paths. Then there is a set $\mathcal{P}$ of pairwise disjoint paths in $G$, such that for every $0\leq i<j \leq n$, at least $k_{i,j}$ elements of $\mathcal{P}$ meet both $L_i$,$L_j$.

Menger's theorem says that the maximum number of pairwise disjoint paths between two vertex sets $L,R$ of a graph G equals the minimum size of an $L$-$R$ separator. Below is a generalisation with more than two vertex sets, arranged in a liner fashion, and a set of paths that simultaneously saturates all pairs of these vertex sets. The question is if this is known:

enter image description here Let $G$ be a finite graph, and $L_i, 0 \leq i \leq n$, a family of disjoint vertex sets of $G$, such that each $L_i, 0 < i < n$ separates $L_{i-1}$ from $L_{i+1}$. Let $k_{i,j}$ denote the maximum number of pairwise disjoint $L_i$-$L_j$ paths. Then there is a set $\mathcal{P}$ of pairwise disjoint paths in $G$, such that for every $0\leq i<j \leq n$, at least $k_{i,j}$ elements of $\mathcal{P}$ meet both $L_i$,$L_j$.

Source Link
Agelos
  • 1.9k
  • 10
  • 17

A multi-layer version of Menger's theorem

Menger's theorem says that the maximum number of pairwise disjoint paths between two vertex sets $L,R$ of a graph G equals the minimum size of an $L$-$R$ separator. Below is a generalisation with more than two vertex sets, arranged in a liner fashion, and a set of paths that simultaneously saturates all pairs of these vertex sets. The question is if this is known:

enter image description here Let $G$ be a finite graph, and $L_i, 0 \leq i \leq n$, a family of disjoint vertex sets of $G$, such that each $L_i, 0 < i < n$ separates $L_{i-1}$ from $L_{i+1}$. Let $k_{i,j}$ denote the maximum number of pairwise disjoint $L_i$-$L_j$ paths. Then there is a set $\mathcal{P}$ of pairwise disjoint paths in $G$, such that for every $0\leq i<j \leq n$, at least $k_{i,j}$ elements of $\mathcal{P}$ meet both $L_i$,$L_j$.