| doi:10.2201/NiiPi.2012.9.7 |
| An immersion of a square in 4-edge-connected graphs |
| Ken-ichi KAWARABAYASHI1 and Yusuke KOBAYASHI2 |
1National Institute of Informatics
2University of Tokyo |
(Received: November 14,2011)
(Revised: )
(Accepted: December 22,2011) |
Abstract:
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.
|
Keywords:
graph algorithm, immersion, edge-connectivity, edge-disjoint paths
|
|
|
| PDF(110KB) | References |
National Institute of Informatics is a member of CrossRef.
|
