Premium
Vertex‐disjoint paths and edge‐disjoint branchings in directed graphs
Author(s) -
Whitty R. W.
Publication year - 1987
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190110309
Subject(s) - combinatorics , mathematics , disjoint sets , conjecture , vertex (graph theory) , constructive , constructive proof , discrete mathematics , graph , computer science , operating system , process (computing)
A theorem of J. Edmonds states that a directed graph has k edge‐disjoint branchings rooted at a vertex r if and only if every vertex has k edge‐disjoint paths to r . We conjecture an extension of this theorem to vertex‐disjoint paths and give a constructive proof of the conjecture in the case k = 2.