No label defined (Q4936766)

In many combinatorial optimization problems, it is worth considering the convex hull of the set of admissible solutions. Sometimes the combinatorial properties of this polytope are important in designing algorithms that solve the problem at hand. The article under review deals with the polytope \({\mathcal P_k}(G)\) of \(k\)-factors in a graph \(G\) and gives some necessary and sufficient combinatorial conditions for the adjacency of vertices of \({\mathcal P_k}(G)\). A sample result is as follows: If the symmetric difference of two \(k\)-factors induces either an even cycle or a pair of odd cycles with precisely one vertex in common, then the corresponding vertices of \({\mathcal P_k}(G)\) are adjacent. For the entire collection see [Zbl 0889.00011].