From edge-disjoint paths to independent paths

arXiv1203.4483MaRDI QIDQ6231741FDOQ6231741

Publication date: 20 March 2012

Abstract: Let f(k) denote the maximum such that every simple undirected graph containing two vertices s,t and k edge-disjoint s-t paths, also contains two vertices u,v and f(k) independent u-v paths. Here, a set of paths is independent if none of them contains an interior vertex of another. We prove that f(k)=k if k<3, and f(k)=3 otherwise.

This page was built for publication: From edge-disjoint paths to independent paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6231741)