Graph orientations with set connectivity requirements

详细信息	查看全文 | 推荐本文 |

• 作者：Takuro Fukunaga ^{takuro@amp.i.kyoto-u.ac.jp}
• 关键词：Edge-connectivity ; Graph orientation ; Group Steiner tree packing
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：6 August, 2012
• 卷：312
• 期：15
• 页码：2349-2355
• 文件大小：261 K

摘要

In an undirected or a directed graph, the edge-connectivity between two disjoint vertex sets and is defined as the minimum number of edges or arcs that should be removed for disconnecting all vertices in from those in . This paper discusses how to construct a directed graph from a given undirected graph by orienting edges so as to preserve the edge-connectivity on pairs of vertex sets as much as possible. We present several bounds on the gap between the edge-connectivities in the undirected graph and in the obtained directed graphs, which extends the Nash-Williams鈥?strong orientation theorem.