Published online by Cambridge University Press: 05 May 2012
For an eulerian weighted graph (G, w), if (G, w) is a contra pair, can we find another admissible eulerian weight w* of G such that (G, w*) remains as a contra pair while w*(G) < w(G) and 0 ≤ w*(e) ≤ w(e) for every edge e? If the answer to this question is “yes,” then we should concentrate on eulerian (1, 2)-weights in the study of contra pairs.
It is obvious that every bridgeless graph has a circuit cover. However, we do not know yet how “small” the maximum coverage would be. If one is able to find another circuit cover that reduces the coverage while the parity of coverage is retained, then one is able to reduce the coverage recursively down to 1 or 2, and the CDC conjecture is followed.
These two problems are both related to reductions: reduction of weight in a contra pair, and reduction of coverage of an existing cover. The first problem has a complete answer, and is studied in Section 12.1. The second problem, as we can see already, remains as an approach to the CDC conjecture (Section 12.2).
Note that reduction of total coverage without preserving the parity of coverage is the shortest cycle cover problem, which is discussed separately in Chapter 14.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.