umu.sePublications
Change search

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
On stable cycles and cycle double covers of graphs with large circumference
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2012 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 17, p. 2540-2544Article in journal (Refereed) Published
##### Abstract [en]

A cycle C in a graph is called stable if there exists no other cycle D in the same graph such that V(C)⊆V(D). In this paper, we study stable cycles in snarks and we show that if a cubic graph G has a cycle of length at least |V(G)|−9 then it has a cycle double cover. We also give a construction for an infinite snark family with stable cycles of constant length and answer a question by Kochol by giving examples of cyclically 5-edge connected snarks with stable cycles.

##### Place, publisher, year, edition, pages
Elsevier, 2012. Vol. 312, no 17, p. 2540-2544
##### Keyword [en]
Stable cycle, Snark, Cycle double cover, Semiextension
##### National Category
Discrete Mathematics
Mathematics
##### Identifiers
ISI: 000306873100004OAI: oai:DiVA.org:umu-53282DiVA, id: diva2:511319
##### Conference
the 8th French Combinatorial Conference, 28 June - 2 July, 2010, Paris
##### Note

Special Issue: Proceedings of the 8th French Combinatorial Conference

Available from: 2012-03-21 Created: 2012-03-19 Last updated: 2017-12-07Bibliographically approved
##### In thesis
1. Snarks: Generation, coverings and colourings
Open this publication in new window or tab >>Snarks: Generation, coverings and colourings
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

For a number of unsolved problems in graph theory such as the cycle double cover conjecture, Fulkerson's conjecture and Tutte's 5-flow conjecture it is sufficient to prove them for a family of graphs called snarks. Named after the mysterious creature in Lewis Carroll's poem, a \emph{snark} is a cyclically 4-edge connected 3-regular graph of girth at least 5 which cannot be properly edge coloured using three colours. Snarks and problems for which an edge minimal counterexample must be a snark are the central topics of this thesis.

The first part of this thesis is intended as a short introduction to the area. The second part is an introduction to the appended papers and the third part consists of the four papers presented in a chronological order.

In Paper I we study the strong cycle double cover conjecture and stable cycles for small snarks. We prove that if a bridgeless cubic graph $G$ has a cycle of length at least $|V(G)|-9$ then it also has a cycle double cover. Furthermore we show that there exist cyclically 5-edge connected snarks with stable cycles and that there exists an infinite family of snarks with stable cycles of length 24.

In Paper II we present a new algorithm for generating all non-isomorphic snarks with a given number of vertices. We generate all snarks on 36 vertices and less and study these with respect to various properties. We find that a number of conjectures on cycle covers and colourings holds for all graphs of these orders. Furthermore we present counterexamples to no less than eight published conjectures on cycle coverings, cycle decompositions and the general structure of regular graphs.

In Paper III we show that Jaeger's Petersen colouring conjecture holds for three infinite families of snarks and that a minimum counterexample to this conjecture cannot contain a certain subdivision of $K_{3,3}$ as a subgraph. Furthermore, it is shown that one infinite family of snarks have strong Petersen colourings while another does not have any such colourings.

Two simple constructions for snarks with arbitrary high oddness and resistance is given in Paper IV. It is observed that some snarks obtained from this construction have the property that they require at least five perfect matchings to cover the edges. This disproves a suggested strengthening of Fulkerson's conjecture.

##### Place, publisher, year, edition, pages
Umeå: Umeå universitet, 2012. p. 69
##### Series
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 53
##### Keyword
Snarks, cubic graphs, enumeration, cycle covers, perfect matching covers, Fulkerson's conjecture, strong cycle double cover conjecture, cycle decompositions, stable cycles, oddness, circumference, uncolourability measures
##### National Category
Discrete Mathematics
Mathematics
##### Identifiers
urn:nbn:se:umu:diva-53337 (URN)978-91-7459-399-0 (ISBN)
##### Public defence
2012-04-13, MIT-huset, MA121, Umeå universitet, Umeå, 13:15 (English)
##### Supervisors
Available from: 2012-03-23 Created: 2012-03-21 Last updated: 2013-09-05Bibliographically approved

#### Open Access in DiVA

No full text in DiVA

Publisher's full text

#### Search in DiVA

##### By author/editor
Hägglund, JonasMarkström, Klas
##### By organisation
Department of Mathematics and Mathematical Statistics
##### In the same journal
Discrete Mathematics
##### On the subject
Discrete Mathematics

doi
urn-nbn

#### Altmetric score

doi
urn-nbn
Total: 196 hits

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf