We give an approximate Menger-type theorem for the case when a graph G contains two X - Y paths P 1 and P 2 such that P 1 \cup P 2 is an induced subgraph of G . More generally, we prove that there exists a function f ( d ) \in O ( d ), such that for every graph G and X, Y \subseteq V ( G ), either there exist two X - Y paths P 1 and P 2 such that the distance between P 1 and P 2 is at least d , or there exists v \in V ( G ) such that the ball of radius f ( d ) centered at v intersects every X - Y path.
A Menger-Type Theorem for Two Induced Paths / Albrechtsen, Sandra; Huynh, Tony; Jacobs, Raphael W.; Knappe, Paul; Wollan, Paul. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - 38:2(2024), pp. 1438-1450. [10.1137/23m1573082]
A Menger-Type Theorem for Two Induced Paths
Huynh, Tony;Wollan, Paul
2024
Abstract
We give an approximate Menger-type theorem for the case when a graph G contains two X - Y paths P 1 and P 2 such that P 1 \cup P 2 is an induced subgraph of G . More generally, we prove that there exists a function f ( d ) \in O ( d ), such that for every graph G and X, Y \subseteq V ( G ), either there exist two X - Y paths P 1 and P 2 such that the distance between P 1 and P 2 is at least d , or there exists v \in V ( G ) such that the ball of radius f ( d ) centered at v intersects every X - Y path.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
