摘要：For an undirected graph G and its four distinct vertices v1, v2, v3, v4, an immersion of (v1, v2, v3, v4) is a subgraph of G that consists of four edge-disjoint paths P1, P2, P3, P4 such that Pi connects vi and vi+1 for i=1, 2, 3, 4, where v5=v1. We show that every 4-edge-connected graph G = (V, E) has an immersion of (v1, v2, v3, v4) for any v1, v2, v3, v4 ∈ V, and it can be found in linear time.
Loading...
