Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2006-006 (May 08, 2006)

Eulerian Detachments with Local-Edge-Connectivity
by Takuro Fukunaga and Hiroshi Nagamochi

pdf File


For a graph G, a detachment operation at a vertex transforms the graph into a new graph by splitting the vertex into several vertices in such a way that the original graph can be obtained by contracting all the split vertices into a single vertex. A graph obtained from a given graph G by applying detachment operations at several vertices is called a detachment of graph G. We consider a detachment which preserves the local-edge-connectivity of the given graph G. In this paper, we present necessary and sufficient conditions for a given graph/digraph to have an r-edge-connected Eulerian detachment. We also discuss conditions for a graph/digraph to admit a loopless r-edge-connected Eulerian detachment.