Skip to main content Accessibility help
×
Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-23T09:19:53.146Z Has data issue: false hasContentIssue false

9 - Girth, embedding, small cover

Published online by Cambridge University Press:  05 May 2012

Cun-Quan Zhang
Affiliation:
West Virginia University
Get access

Summary

Girth

The girth of a smallest counterexample to the circuit double cover was first studied by Goddyn [82], in which, a lower bound 7 of girth was found. Later, this bound was improved as follows: at least 8 by McGuinness [179], and at least 9 by Goddyn [83] (a girth bound of 10 was also announced in [83]). The following theorem, proved with a computer aided search, remains the best bound up to today.

Theorem 9.1.1 (Huck [115]) The girth of a smallest counterexample to the circuit double cover conjecture is at least 12.

It was conjectured in [132] that cyclically 4-edge-connected snarks may have bounded girths. If this conjecture were true, then the circuit double cover conjecture would be followed immediately by Theorem 9.1.1 (or an earlier result in [82] for girth 7). But this is not the case: in [146], Kochol gave a construction of cyclically 5-edge-connected snarks of arbitrarily large girths.

However, Theorem 9.1.1 (or its earlier results) remains useful in the studies of some families of embedded graphs with small genus since the girth of such graphs is bounded (see Section 9.2).

Small genus embedding

The circuit double cover conjecture is trivial if a bridgeless graph is planar: the collection of face boundaries is a double cover. How about graphs embeddable on surfaces other than a sphere? Although it is known that every bridgeless graph has a 2-cell embedding on some surface, it is not guaranteed that face boundaries are circuits (see Section 1.4).

Type
Chapter
Information
Publisher: Cambridge University Press
Print publication year: 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Save book to Kindle

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.

Available formats
×

Save book 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 Dropbox.

Available formats
×

Save book to Google Drive

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.

Available formats
×