Premium
Edge disjoint Steiner trees in graphs without large bridges
Author(s) -
Kriesell Matthias
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20389
Subject(s) - combinatorics , mathematics , vertex (graph theory) , neighbourhood (mathematics) , disjoint sets , graph , bound graph , connectivity , spanning tree , discrete mathematics , graph power , line graph , mathematical analysis
A set A of vertices of an undirected graph G is called k ‐ edge‐connected in G if for all pairs of distinct vertices a, b ∈ A , there exist k edge disjoint a, b ‐paths in G . An A ‐ tree is a subtree of G containing A , and an A ‐ bridge is a subgraph B of G which is either formed by a single edge with both end vertices in A or formed by the set of edges incident with the vertices of some component of G − A . It is proved that (i) if A is k ·(ℓ + 2)‐edge‐connected in G and every A ‐bridge has at most ℓ vertices in V ( G ) − A or at most ℓ + 2 vertices in A then there exist k edge disjoint A ‐trees, and that (ii) if A is k ‐edge‐connected in G and B is an A ‐bridge such that B is a tree and every vertex in V ( B ) − A has degree 3 then either A is k ‐edge‐connected in G − e for some e ∈ E ( B ) or A is ( k − 1)‐edge‐connected in G − E ( B ). © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 188–198, 2009