Odd vertex pairing
Let G=(V,E) be an undirected graph. An odd vertex pairing of G is a new graph whose node set is the set of odd degree nodes of G, and in which every node has degree 1.
For a node set [math]\emptyset \neq X \subsetneq V[/math], let [math]R_G(X)=\max\{\lambda_G(u,v):\ u \in X, v\notin X\},[/math] where [math]\lambda_G(u,v)[/math] is the local edge-connectivity between u and v.
An odd vertex pairing M of G is feasible if [math]\frac{d_G(X)-d_M(X)}{2} \geq \left\lfloor\frac{R_G(X)}{2}\right\rfloor[/math] for every [math]\emptyset \neq X \subsetneq V[/math].
The existence of a feasible odd vertex pairing for any graph G was proved by Nash-Williams [1], see Nash-Williams' strong orientation theorem. Gabow [2] developed an efficient algorithm to find one. Further properties of odd vertex pairings have been investigated by Király and Szigeti [3].
References
- ↑ C. St. J. A. Nash-Williams, On orientations, connectivity and odd vertex pairings in finite graphs, Canad. J. Math. 12 (1960) 555-567, journal link
- ↑ H. N. Gabow, Efficient splitting off algorithms for graphs, DOI link.
- ↑ Z. Király, Z. Szigeti, Notes on well-balanced orientations, EGRES Technical Report
