| Full text | |
| Author(s): |
Ali, Alonso
;
Lee, Orlando
Total Authors: 2
|
| Document type: | Journal article |
| Source: | XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023; v. 224, p. 8-pg., 2023-01-01. |
| Abstract | |
Let G be a graph and let r be a fixed vertex of G. Two spanning trees T-1 and T-2 of G rooted at r are edge-independent if for every vertex v is an element of V(G), the paths from v to r in T-1 and from v to r in T-2 are edge-disjoint. Itai and Zehavi conjectured that for every k-edge-connected graph and any vertex r is an element of V(G) there are k edge-independent spanning trees rooted at r (Edge-Independent Spanning Trees Conjecture). Itai and Rodeh proved the case k =2, Schlipf and Schmidt proved the case k = 3, and Hoyer and Thomas proved the case k = 4 of the conjecture. In this paper, we prove the case k = 5. (C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0) (AU) | |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 20/11118-6 - Graph connectivity |
| Grantee: | Alonso Ali Gonçalves |
| Support Opportunities: | Scholarships in Brazil - Doctorate |