Eulerian detachments with local edge-connectivity |
| |
Authors: | Takuro Fukunaga Hiroshi Nagamochi |
| |
Affiliation: | Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, Japan |
| |
Abstract: | 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. While detachment operations may decrease the connectivity of graphs, there are several works on conditions for preserving the connectivity. In this paper, we present necessary and sufficient conditions for a given graph/digraph to have an Eulerian detachment that satisfies a given local edge-connectivity requirement. We also discuss conditions for the detachment to be loopless. |
| |
Keywords: | Edge-splitting Eulerian graphs Detachment Local edge-connectivity |
本文献已被 ScienceDirect 等数据库收录! |