The faithful covering problem is introduced as a natural approach for the CDC conjecture. Although the faithful covering problem does not hold for all eulerian (1, 2)-weighted graphs ((*P*_{10}, *w*_{10}) is a counterexample), there are some generalizations and relaxations. Theorem 12.1.2 can be considered as a general faithful covering problem for all positive weights, while Theorem 15.1.2, Propositions 15.2.1 and 15.2.2, etc. are all considered as relaxations of the faithful covering problem.

Most of the related faithful covering problems have similar definitions in graph theory and in linear/integer programming.

**Definition 15.0.1** Let *G* = (*V, E*) be a bridgeless graph ...

Start Free Trial

No credit card required