Highly connected infinite digraphs without edge-disjoint back and forth paths between a certain vertex pair

2025-02-10
15:00-16:00
FAMNIT-MP1
Attila Joó (University of Hamburg)
Highly connected infinite digraphs without edge-disjoint back and forth paths between a certain vertex pair

A theorem of Mader states that in every finite (k+1)-edge-connected digraph D, for any s, t ∈ V(D), there exists an st-path P such that D – E(P) remains k-edge-connected. We show that this result does not extend to infinite digraphs and can fail drastically. Specifically, for every k ∈ ℕ, we construct a "fractal-like" infinite k-edge-connected digraph Dk with s, t ∈V(Dk), in which every st-path shares an edge with every ts-path.

Delite z drugimi

Leave a Reply

Vaš e-naslov ne bo objavljen. * označuje zahtevana polja

Orodna vrstica za dostopnost