Splitting Off Edges within a Specified Subset Preserving the Edge-Connectivity of the Graph
✍ Scribed by Jørgen Bang-Jensen; Tibor Jordán
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 141 KB
- Volume
- 37
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
Splitting off a pair su sv of edges in a graph G means the operation that deletes su and sv and adds a new edge uv. Given a graph G = V + s E which is kedge-connected (k ≥ 2) between vertices of V and a specified subset R ⊆ V , first we consider the problem of finding a longest possible sequence of disjoint pairs of edges sx sy, (x y ∈ R) which can be split off preserving k-edge-connectivity in V . If R = V and d s is even then a well-known theorem of Lovász asserts that a complete R-splitting exists, that is, all the edges connecting s to R can be split off in pairs. This is not the case in general. We characterize the graphs possessing a complete R-splitting and give a formula for the length of a longest R-splitting sequence. Motivated by the connection between splitting off results and connectivity augmentation problems we also investigate the following problem that we call the split completion problem: given G and R as above, find a smallest set F of new edges incident to s such that G = V + s E + F has a complete R-splitting. We give a min-max formula for F as well as a polynomial algorithm to find a smallest F. As a corollary we show a polynomial algorithm which finds a solution of size at most k/2 + 1 more than the optimum for the following augmentation problem, raised in [2]: given a graph H = V E , an integer k ≥ 2, and a set R ⊆ V , find a smallest set F of new edges for which H = V E + F is k-edge-connected and no edge of F crosses R.
📜 SIMILAR VOLUMES
We prove that every connected graph on n vertices can be covered by at most nÂ2+O(n 3Â4 ) paths. This implies that a weak version of a well-known conjecture of Gallai is asymptotically true.
It is known that a noncomplete }-connected graph of minimum degree of at least w 5} 4 x contains a }-contractible edge, i.e., an edge whose contraction yields again a }-connected graph. Here we prove the stronger statement that a noncomplete }-connected graph for which the sum of the degrees of any
In this article, we study the existence of a 2-factor in a K 1,nfree graph. Sumner [J London Math Soc 13 (1976), 351-359] proved that for n ≥ 4, an (n-1)-connected K 1,n -free graph of even order has a 1-factor.