首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号